Sort an Array According to the Relative Order of Another Array

Approach 2

Make Use of Hashing

The goal is to keep track of the frequency of each element of the first array in a hash table.

Algorithm

• Check whether or not each element of the second array is present on the map.
• Print the element n times if it appears on the map, where n is the frequency of that element in the first array.
• We also remove that element from the map, leaving only the elements in the first array that are present (but not present in the second array).
• They must be sorted before being added at the end.
• Although keys in std::map or TreeMap are already ordered, the insertion and retrieval times are O(log(n)).
• We get O(1) insertion and retrieval time if we use std::unordered map or HashMap, but we'll have to sort because the keys aren't in any particular order.

The following is how the above strategy is put into action:

Implementation C++

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
void hashingSort(int first[], int second[], int p, int q)

{
unordered_map<int, int> freq;  
for (int i = 0; i < p; i++) 
   {
    freq[first[i]]++;
   }

   int index = 0;
   for (int i = 0; i < q; i++)
   {
      while (freq[second[i]])
   {
      first[index++] = second[i];
      freq[second[i]]--;
   }   
      freq.erase(second[i]);
   }    

int i = index;
for (auto it = freq.begin(); it != freq.end(); it++)
    {
       while (it->second--) 
      {
        first[index++] = (it->first);
      }
    }
     sort(first + i, first + index);
}

void printArray(int arr[], int q)
   {
     for (int i = 0; i < q; i++) 
   {
     cout << arr[i] << " ";
   }
     cout << endl;
   } 

//Main Function of the program
int main()
{
int first[] = { 5, 8, 9, 3, 5, 7, 1, 3, 4, 9, 3, 5, 1, 8, 4 };
int second[] = { 3, 5, 7, 2 };
int p = sizeof(first) / sizeof(first[0]);
int q = sizeof(second) / sizeof(second[0]);
hashingSort(first, second, p, q);
cout << "The array after being sorted through hashing is ";
printArray(first, p);
return 0;
}

Output

The array after being sorted through hashing is 3 3 3 5 5 5 7 1 1 4 4 8 8 9 9 

Complexity
 

Time complexity: 
The above solution has an O(mlog(m) + n) time complexity, where m and n are the total number of elements in the first and second arrays, respectively.

Under the assumption that the hashing function takes O(log(n)) insertion and retrieval time, checking each element in the second array and printing all elements that appear in the hashmap on average O(m+n) time.

Space Complexity: O(n), with the increase in the number of entries the size of the hashmap increases linearly.
 

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What is a relative order array, and how does it work?

Programming. Assume we have two arrays, arr1 and arr2, each with its own set of elements, and all of the elements in arr2 are also present in arr1. We must sort the elements of arr1 so that the relative ordering of items in arr1 matches the relative sequence of items in arr2.

How should two arrays be sorted in the same order?

• Make a list of the main array's indexes (sortableArray)
• Using a custom comparison, sort the indexes.
• The index is used to look up the function that compares the values.
• Map each index to its value for each input array.

How do you combine two arrays in the most efficient way?

We calculate their length and store it in the fal and sal variables to merge two arrays. We create a new integer array result that holds the sum of both arrays' lengths. Using the arraycopy() function, copy each element of both arrays to the result array.

Can you think of a way to combine two separately sorted arrays into a single sorted array?

Make an array of size n1 + n2 called arr3[].Traverse arr1[] and arr2[] at the same time. Pick the smallest of the current elements in arr1[] and arr2[], copy it to the next position in arr3[], and move forward in arr3[] and the array whose element is picked.

Conclusion

As discussed in this article, the problem "Sort an array according to the order defined by another array" asks you to sort the first array according to the second array so that the numbers in the first array are sorted relative to all of the values in the arr2[] array. We use Hash Ordered Map to get the desired result.

We hope that this article has helped you enhance your knowledge regarding the subject of Array and relative sorting.

After reading about the sorting of arrays, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about array sorting algorithms, maximum sum such that no two elements are adjacent, and Finding maximum repeating number in an array  Also see time complexity and Complexity Analysis.

You can also practice some relevant problems at Coding Ninjas Studio such as:

1. Sum of the infinite array
2. Maximum Subarray Sum
3. First missing positive
4. Aggressive Cows
5. K largest element and many more.
    

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!