# 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:**

- The elements of
**set 2**must be distinct. - 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:**

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

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.

Thanks for sharing this.