Be the first user to complete this post
|
Add to List |
57. Sort an Array According to the Order Defined by Another Array
Objective: Given an array of integers, write an algorithm to sort it according to the order defined by another array.
Input Array: 2 6 9 1 4 4 2 1 10 13 5 7 8 DefinedArray: 1 2 4 6 Output: 1 1 2 2 4 4 6 5 7 8 9 10 13
Method 1: Sort and Search
- Let's say two given arrays are InputArray and DefinedArray.
- Create an Aux array and copy all the elements of the InputArray.
- Create another boolean array, of the size InputArray
- Sort Aux array.
- Navigate through the DefinedArray and for each element x,
- Perform a binary search of x on the Aux array and find the first occurrence of x. If x is found, copy it to InputArray and mark it visited in the boolean array.
- Do scan on the Aux array, copy all the occurrences of x to InputArray, and mark all these indexes true in the boolean array.
- When DefinedArray is over, copy the rest of the elements (non-visited) from Aux to InputArray.
Original Array : 2 6 9 1 4 4 2 1 10 13 5 7 8 Defined Array : 1 2 4 6 Output Array using Sort and search: 1 1 2 2 4 4 6 5 7 8 9 10 13
Method 2: Using Hashing
- Let's say two given arrays are InputArray and DefinedArray.
- Insert all the elements of InputArray in a Map. Element as key and its count as its value
- Navigate through the DefinedArray and for each element x,
- Check if the element is present in the Map, If yes then take its value (count) and insert those many x in the InputArray
- Once DefinedArray is completed, take the rest of the elements from the Map, sort, and insert them into InputArray
Original Array : 2 6 9 1 4 4 2 1 10 13 5 7 8 Defined Array : 1 2 4 6 Output Array using Hashing : 1 1 2 2 4 4 6 5 7 8 9 10 13