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++ implementation –
 

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 implementation –
 

Download   Run Code

Output:

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of