Home » Interview coding problems/challenges

Relative sorting algorithm

In this article, we are going to learn relative sorting along with its algorithm, C++ program.
Submitted by Radib Kar, on November 20, 2018

Description: This a coding problem came in the coding round of Amazon, Microsoft.

Problem Statement:

Given two array A and B, sort A in such a way that the relative order among the elements will be the same as those in B. For the elements not present in B, append them at last in sorted order. It is also given that the number of elements in B is smaller than or equal to the number of elements in A and B has all distinct elements.

Solution

Algorithm:

1. To solve the above problem vector is used to implement the arrays.
2. Initialize three vectors.

Vector<int> a: for array A
Vector<int> b: for array B
Vector<int> c: for output array (relatively sorted array)

3. Take input for array A and B
4. Sort vector a using in-build sorting function.
5. For sorting the elements of a according to order of b,

For i=0:n2-1      //n2 be the no of elements of B&n1 of A
    For  j=0:n1-1 && a[j]<=b[i]    //maintaining the order of b
        if(a[j]==b[i])
            inserta[j] into c;
            Set a[j] to 0 for avoiding duplication
        End if
    End For loop
End For loop

6. The elements of vector a, also presented in vector b are sorted according to relative order of vector b. The rest of vector a is to be appended at the end of vector c in sorted way.
7. Just appended the rest of elements of vector a in vector c. (elements those are not zero).
8. vector c is the desired output.

C++ program to implement relative sorting algorithm

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

vector<int> sorted(vector<int> a,vector<int> b,int n1,int n2){
	vector <int> c;
	// array a is sorted using labrary sorting function
	sort(a.begin(),a.end()); 

	for(int i=0;i<n2;i++){
		for(int j=0;j<n1 && a[j]<=b[i];j++){
			// elements of sorted a is entered to array c 
			// maintaing the element order as in b
			if(a[j]==b[i]){
				c.push_back(a[j]);
				//clear the element pushed into c
				a[j]=0;
			}
		}
	}

	// the elements that are not in b is in being entered to c 
	// in sorted manner as a is already sorted
	for(int i=0;i<n1;i++)  
		if(a[i]!=0)    //remaining elements of a
			c.push_back(a[i]);
			
	//return the output
	return c; 
}


int main() {
	int n1,n2,u;
	vector<int> :: iterator p; //iterator p

	scanf("%d %d",&n1,&n2);

	vector<int> a; //array a
	vector<int> b;//array b

	for(int j=0;j<n1;j++){
		scanf("%d",&u);
		// inputing elements of array a
		a.push_back(u); 
	}
	for(int j=0;j<n2;j++){
		scanf("%d",&u);
		// inputing elements of array b
		b.push_back(u);  
	}

	// implemented relative sorting function
	vector<int> c=sorted(a,b,n1,n2); 
	for(p=c.begin();p!=c.end();p++)	
		printf("%d ",*p);  // printing the sorted array
	printf("\n");

	return 0;
}

Output

enter length of array A & B respectively 
10 
5
enter elements of array A
2 5 12 2 8 9 13 5 8 12 
enter elements of array B
5 2 8 12 9 
printing the relatively sorted array 
5 5 2 2 8 8 12 12 9 13