Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Sort an Given Array in the order defined by another array

Objec­tive: Given an array of inte­gers, write an algo­rithm to sort it accord­ing to the order defined by another array.

Input: An Array of Integers

Exam­ple:

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. Cre­ate an Aux array and copy all the ele­ments of arrA
  2. Cre­ate another boolean array, vis­ited[] of size arrA[]
  3. Ini­tial­ize vis­ited[] = false
  4. Sort the Aux array using Merge sort.
  5. Nav­i­gate through the arrB, tak­ing one ele­ment at a time, say x
  6. per­form binary search of x on Aux array and find the first occur­rence of x
  7. if x is found, copy it to arrA, make vis­ited[] = true
  8. Do lin­ear nav­i­ga­tion on Aux array till you find x, copy all these to arrA and mark vis­ited[] = true
  9. When arrB is over, copy rest of the ele­ments from Aux to arrA.

Method 2: Using Hashing

    1. Insert all the ele­ments of arrA in hash Table,
    2. Ele­ment as key and its count as its value
    3. Nav­i­gate through arrB, check element’s pres­ence in Hash table
    4. If it is present then takes its value (count) and insert into arrA.
    5. Once arrB is com­pleted, take rest of the ele­ments from Hash table
    6. Sort Them and insert into arrB.

Com­plete Code:


Out­put:

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

You may also like...