Custom Sort | Sort array based on another array

Given two arrays, reorder elements of first array by order of elements defined by the second array.

Elements which are not present in the second array but present in first array should be appended in the end sorted. Second array can contain some extra elements which are not part of first array.

 
For example,

Input:
arr1 = [5, 8, 9, 3, 5, 7, 1, 3, 4, 9, 3, 5, 1, 8, 4]
arr2 = [3, 5, 7, 2]

Output: [3 3 3 5 5 5 7 1 1 4 4 8 8 9 9]
 


 

Approach 1: (Using Hashing)

 

The idea is to count frequency of each element of first array and store it in a map. Now for each element of second array, we check if the element is present in the map or not. If it is present in the map, then we print the element n number of times where n is the frequency of that element in first array. We also remove that element from the map so that we are only left with elements that are only present in the first array (but not present in the second array). In order to append them in the end, they need to be sorted.

Note that if we use std::map, we have O(log n) insertion, retrieval time but keys are already ordered, so no need to sort. If we use std::unordered_map, we have O(1) insertion, retrieval time but its keys are unordered, so we need to sort the keys..

C++

Download   Run Code

Output:

After sorting the array is : 3 3 3 5 5 5 7 1 1 4 4 8 8 9 9


 

Time complexity of above solution is O(mlogm) + n where m and n is number of elements in the first and second array respectively.

 

Approach 2: (Using comparator in Java)

 

We can also write a custom compare method to solve this problem. Let the two element to be compared are x and y. Then

  1. If both x and y are present in the second array, then the element with lower index in the second array should come first.
     
  2. If only one of x or y is present in the second array, then the element which is present in the second array should come first.
     
  3. If both elements are not present in second array, then the default ordering will be considered.
     

Java

Download   Run Code

Output:

3 3 3 5 5 5 7 1 1 4 4 8 8 9 9

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂