Medium

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
```