Sort an array according to the order defined by another array | faceprep

Sort an array according to the order defined by another array | faceprep

Program to Sort an array according to the order defined by another array is discussed here. Given two arrays A [] and B [], sort A in such a way that the relative order among the elements will be the same as those are in B. The elements in array A has to be printed according to the sequence of order of elements specified in array B, the rest of the elements, remaining in array A are printed at the end.




Solution to this problem can be provided in two different ways

Method 1: Traverse array 2 elements and check if those elements are found in array 1. Perform a binary search to find the elements. If array 2 elements are found in array 1, print them. Print all the remaining elements from array 1 at the end.


Sort an Array According to the Order defined by Another array




Method 2: Store all the array 1 elements in a hashmap. Then, traverse array 2 and check if the element is present in the map. If present, print the element k number of times where k is the frequency of appearance of the element. Then, print the remaining elements of array 1.

For example,

Array A [] = {3, 6, 13, 3, 9, 10, 14, 6, 9, 13}

Array B[] = {6, 3, 9, 13, 10}

Output: {6, 6, 3, 3, 9, 9, 13, 13, 10, 14}




Algorithm to sort an array according to the order defined by another array

  1. Input both the arrays, arr 1 and arr 2.
  2. Traverse the elements of arr 2 from i = 1 to length(arr 2).
  3. Check if arr 1 contains the ith element of arr 2 (Binary search)
  4. Print all the ith elements.
  5. Go to step 2 until all the elements of arr 2 have been traversed.
  6. If there are any remaining elements in arr 1, print them.




Program to sort an array according to the order defined by another array is given below.

@@coding::1@@


Algorithm to sort an array according to the order specified by another array using hashing

  1. Input the array 1 and array 2 elements.
  2. Count the frequency of all the elements of array 1 and store it in a map.
  3. Now, for each element of array 2, check if the element is found in the map.
  4. If it is present, print the number k times, where k is the frequency of appearance of the element.
  5. After printing, remove the element from the map.
  6. After all the array 2 elements have been traversed, sort the remaining elements and print them.

Program to sort elements according to the order specified by another array using hashing is given below.

@@coding::2@@


Recommended Programs



c