Relative Sorting Algorithm and Implementation in C++

In this tutorial, we will learn the relative sorting algorithm and its implementation in C++.

Relative Sorting

Relative sorting algorithm: is a sorting algorithm in which we have to sort elements of set 1 in such a way that the relative ordering of elements in set 1 is the same as in set 2.

Requirements to perform relative sorting:

  1.  The elements of set 2 must be distinct.
  2.  All the elements of set 2 should also be in set 1.

(*Note: Elements which are present in set 1 but not present in set 2 should be placed at the end of a sorted set in ascending order).

Let’s see an example to understand it better.

Example of Relative Sorting

Example:

Set 1= { 2, 5, 3, 4, 8, 3, 3, 7, 11, 4, 3, 9, 5 }

Set 2= { 2, 4, 3, 8, 5 }

Sorted Set= { 2, 4, 4, 3, 3, 3, 8, 5, 5 , 7, 9 , 11 }

In the above example, all the elements of set 2 are distinct and also present in set 1.

The first element of set 2 is 2. So, we will find out all the entries of 2 in set 1. As there is only 1 entry of 2 in a set 1 we will write it in a Sorted Set. The next element of set 2 is 4. So now, we will find out all the entries of 4 in set 1. As there are 2 entries of 4 in set 1 we will write them in the Sorted Set after 2. Likewise, we will find out all the entries for elements 3, 8 and 5 and then we will find out elements that are present in set 1 but not present in set 2. Here, 7, 11 and 9 are such elements. So, we will write them at the end of the Sorted Set in ascending order.

Program to implement Relative Sorting in C++ using Vector

#include<bits/stdc++.h>
#include<vector>        //used for vectors
#include<iterator>      //used for iterators
#include<algorithm>     //used for sort function
using namespace std;

//function declaration
vector<int> relative_sort(vector<int>, vector<int>, int, int);

int main()
{
    int i,n1,n2,m;
    vector<int> :: iterator k;
    vector<int> set1;
    vector<int> set2;
  
    // 'n1' will contain size of set 1
    cout<<"Enter the size of Set 1: ";
    cin>>n1;
    
   // pushing elements in vector 'set 1'
    cout<<"Enter elements of Set 1: ";
    for(i=0; i<n1; i++)
    {
        cin>>m;
        set1.push_back(m);
    }
    
    // 'n2' will contain size of set 2
    cout<<"\nEnter the size of Set 2: ";
    cin>>n2;
    
    // pushing elements in vector 'set 2'
    cout<<"Enter elements of Set 2: ";
    for(i=0; i<n2; i++)
    {
        cin>>m;
        set2.push_back(m);
    }
    
    // Displaying the sorted set
    cout<<"\nSorted Set: ";
    vector<int> sorted_set = relative_sort(set1,set2,n1,n2); 
  for( k=sorted_set.begin(); k!=sorted_set.end(); k++)	
      cout<<*k<<" ";
    
    return 0;
}

vector<int> relative_sort(vector<int> set1,vector<int> set2,int n1,int n2)
{
    int i;
  vector <int> sorted_set;

  /* sort function is an inbuilt function that is used for sorting purpose. begin function returns the starting index of the set and end function returns the last index of the set */
  sort(set1.begin(),set1.end()); 
  
  for(i=0; i<n2; i++)
  {
    for(int j=0; j<n1 && set1[j] <= set2[i]; j++)
    {
      if(set1[j] == set2[i])
      {
        // elements of set 1 are pushing on Sorted set with maintaining element order as in set 2
        sorted_set.push_back(set1[j]);

        //Clear the element pushed into Sorted set
        set1[j]=0;
      }
    }
  }

    //elements which are present in set1 but not present in set 2 are entered in Sorted set in ascending order
    for(i=0; i<n1; i++)  
    if(set1[i]!=0)
      sorted_set.push_back(set1[i]);
      
  return sorted_set; 
}

Input/Output:

Enter the size of Set 1: 8                                                                                                           
Enter elements of Set 1: 2 4 3 6 2 4 9 11                                                                                                                                             

Enter the size of Set 2: 4                                                                                                           
Enter elements of Set 2: 3 2 9 4                                                                                                                                                      

Sorted Set: 3 2 2 9 4 4 6 11

Time complexity

O(n1*n2), Where n1 is no. of elements in Set 1 and n2 is no. of elements in Set 2.

 

You may also read:

  1. Print all the Repeated Numbers with Frequency in an Array in C++
  2. Smallest subarray with k distinct numbers in C++

2 responses to “Relative Sorting Algorithm and Implementation in C++”

  1. Akhil says:

    Very beautifully explained, I thought it would be a difficult topic as none of the other sites have explained it that well. keep it up.

  2. Pranav says:

    Thanks for sharing this.

Leave a Reply

Your email address will not be published. Required fields are marked *