Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

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 into arrB.

Complete Code:


Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: