Be the first user to complete this post

  • 0
 Add to List
Medium

Sort an Given Array in 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: An Array of Integers

Example:

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

Appraoch:

Method 1: Sort and Search

  1. Create an Aux array and copy all the elements of arrA
  2. Create another boolean array, visited[] of size arrA[]
  3. Initialize visited[] = false
  4. Sort the Aux array using Merge sort.
  5. Navigate through the arrB, taking one element at a time, say x
  6. perform binary search of x on Aux array and find the first occurrence of x
  7. if x is found, copy it to arrA, make visited[] = true
  8. Do linear navigation on Aux array till you find x, copy all these to arrA and mark visited[] = true
  9. When arrB is over, copy rest of the elements from Aux to arrA.

Method 2: Using Hashing

  1. Insert all the elements of arrA in hash Table,
  2. Element as key and its count as its value
  3. Navigate through arrB, check element's presence in Hash table
  4. If it is present then takes its value (count) and insert into arrA.
  5. Once arrB is completed, take rest of the elements from Hash table
  6. Sort Them and insert them into arrB.

Code:


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
Output Array using Hashing : 1 1 2 2 4 4 6 5 7 8 9 10 13

Also Read: