Relative Sorting

Task: Given two arrays A and B of size N and M respectively. Sort the array A based on elements in B. If A elements not present in B then append them at the end in sorted order.

Example:

Input:

1

11 4

2 1 2 5 7 1 9 3 6 8 8

2 1 8 3

Output:

2 2 1 1 8 8 3 5 6 7 9

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. int main()
5.  {
6. int t;
7. cin>>t;
8. while(t--)
9. {
10.     int n,m;
11.     cin>>n>>m;
12.     int a[n],b[m];
13.     map<int,int> rs;
14.     for(int i=0;i<n;i++)
15.     {
16.         cin>>a[i];
17.         rs[a[i]]++;
18.     }
19.     for(int i=0;i<m;i++)
20.     {
21.         cin>>b[i];
22.         if(rs.find(b[i])!=rs.end())
23.         {
24.             int t = rs[b[i]];
25.             while(t!=0)
26.             {
27.                 cout<<b[i]<<" ";
28.                 t--;
29.             }
30.             rs.erase(b[i]);
31.         }
32.     }
33.     for(auto i=rs.begin();i!=rs.end();i++)
34.     {
35.         while(i->second--)
36.         {
37.             cout<<i->first<<" ";
38.         }
39.         //rs.erase(i->first);
40.     }
41.     cout<<endl;
42. }
43. return 0;
44. }

---

Here is the Video:

---