Be the first user to complete this post

  • 0
 Add to List
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

Related Problems: