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

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

Insert all the elements of arrA in hash Table,
Element as key and its count as its value
Navigate through arrB, check element’s presence in Hash table
If it is present then takes its value (count) and insert into arrA.
Once arrB is completed, take rest of the elements from Hash table
Sort Them and insert into arrB.
Complete Code for both methods: Run This 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..-

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

Like this: Like Loading...

Related