×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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.

Algorithm

  1. To solve the above problem vector is used to implement the arrays.
  2. Initialize three vectors.
  3. Vector<int> a: for array A
    Vector<int> b: for array B
    Vector<int> c: for output array (relatively sorted array)
    
  4. Take input for array A and B
  5. Sort vector a using in-build sorting function.
  6. For sorting the elements of a according to order of b,
  7. 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
    
  8. 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.
  9. Just appended the rest of elements of vector a in vector c. (elements those are not zero).
  10. 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 


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.