C++ program to sort an array according to the order defined by another array

Hi there. Today we going to see how to sort an array in an order defined by another array in C++. The advantage of this is that you can create custom sorting algorithms.

This is an overview of how the algorithm works. We traverse the entire array which defines the order. And for each element, we search for it in the array we have to sort. We can use any search algorithm for that task. If the element is found, that element will be printed first. The same procedure goes on until there are no more elements in the ordered array. If there are any elements remaining in the first array, we sort them separately, and print them at the last.

C++: sort an array according to the order defined by another array

First, we need to choose an algorithm for searching. Let’s take the binary search algorithm, because the cost of an average case is only O(log N). But before searching, we need to sort the array. So we use the sort method of the STL library. Now, let’s look at the code.

#include <bits/stdc++.h>
using namespace std;

int bs(int l,int h,int x,int n,int a[])
{
    if(h>=l)
    {
        int m=l+(h-l)/2;
        if((m==0 || x>a[m-1]) &&a[m]==x)
        {
            return m;
        }
        if(x>a[m])
        {
            return bs((m+1),h,x,n,a);
    	}
    return bs(l,(m-1),x,n,a);
    }
    return -1;
}

void srt(int n1,int n2,int a1[],int a2[])
{
    int temp[n1],vstd[n1];
    int index=0,b=0;
    for(int o=0;o<n1;o++)
    {
        temp[o] = a1[o];
        vstd[o] = 0;
    }
    sort(temp,temp+n1);
    
    for(int i=0;i<n2;i++)
    {	
        b=bs(0,n1-1,a2[i],n1,temp);
        if(b==-1)
        {
        	continue;
        }
        for(int j=b;(j<n1 && temp[j]==a2[i]);j++)
        {
            a1[index++]=temp[j];
            vstd[j]=1;
        }
    }
    for(int k=0;k<n1;k++)
    {
        if(vstd[k]==0)
        {
            a1[index++]=temp[k];
    	}
    }
}

int main()
{
    int n1,n2;
    cout<<"Enter the number of elements for 1st array:"<<endl;
    cin>>n1;
    cout<<"Enter the number of elements for 2nd array:"<<endl;
    cin>>n2;
    
    int a1[n1];
    int a2[n2];
    cout<<"enter array 1 elements:";    
    for(int i=0;i<n1;i++)
    {
    	cin>>a1[i];
    }
    cout<<"enter array 2 elements:";
    for(int j=0;j<n2;j++)
    {
        cin>>a2[j];
    }
    
    cout<<endl<<"The sorted array becomes:";
    srt(n1,n2,a1,a2);
    for(int u=0;u<n1;u++)
    {
    	cout<<a1[u]<<" ";
    }
    return 0;
}

The code might look a little complex, but it is very easy in implementation. In the main function, we take input the sizes of both the arrays, and then their elements. Then, we call the sort method, which is the main part of our algorithm.

In the sort function, we define another array, which tells if a certain element has been visited or not. If not, then we append them at the end in sorted order. We sort the array first, so that we can use binary search. Then for each element in 2nd array, we search for it in the 1st array using binary search. If the element isn’t found, then it will be added at the end. Otherwise, we keep printing the found element until we reach the end of the array. This continues until we reach the end of the 2nd array. And then, the remaining elements of the 1st array are printed.

Now, let’s look at the output.

Enter the number of elements for 1st array:
8
Enter the number of elements for 2nd array:
4
enter array 1 elements:1 2 3 4 5 6 7 8
enter array 2 elements:6 5 2 4

The sorted array becomes:6 5 2 4 1 3 7 8

As you can see, the 1st array gets sorted in the order defined by the 2nd array. And the remaining elements are added at the end in a sorted manner.

I hope you found this article useful. For further practice, you can use another search algorithm, like linear search, etc. Or you can create a custom sort method and use it with the library function. That will enhance your grasp on the topic.

Also read: Add two numbers without using Arithmetic Operators in C++