Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach 1
2.1.
Algorithm
2.2.
Implementation 
2.2.1.
Complexity Analysis:
3.
Approach 2
3.1.
Algorithm
3.2.
Implementation C++
3.2.1.
Complexity 
4.
Frequently Asked Questions
4.1.
What is a relative order array, and how does it work?
4.2.
How should two arrays be sorted in the same order?
4.3.
How do you combine two arrays in the most efficient way?
4.4.
Can you think of a way to combine two separately sorted arrays into a single sorted array?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sort an Array According to the Relative Order of Another Array

Author Palak Mishra
0 upvote

Introduction

We will learn about the program that sorts an array in the order defined by another array, discussed later. We're given two arrays, A [] and B [], and we need to sort A so that the relative order of the elements matches that of B. The elements in array A must be printed in the order specified in array B, and the remaining elements in array A must be printed at the end.

Problem Statement

Sort P in such a way that the relative order of the elements is the same as it is in Q. Given two arrays, P[] and Q[], sort P so that the relative order of the elements is the same as it is in Q. Append the elements that are missing from Q last, in sorted order.

Sample Examples

Example 1: 

Input:

P[] = {20, 10, 20, 50, 70, 10, 90, 30, 60, 80, 80}
 Q[] = {20, 10, 80, 30}

 

Output: 

P[] = {20, 20, 10, 10, 80, 80, 30, 50, 60, 70, 90}

 

Example 2:

Input: 

P[] ={20,10, 20, 50, 70, 10, 90, 30, 60, 80, 80}
  Q[]={99, 22, 444, 56,}

 

Output: 

P[] ={10, 10, 20, 20, 30, 50, 60, 70, 80, 80, 90}

The code should account for all possible scenarios, such as Q[] having more or fewer elements than P[]. Q[] may contain elements that aren't present in P[] and vice versa.

Approach 1

Make Use of binary search and sorting.

Examine the elements of array 2 to see if they appear in array 1. To find the elements, use a binary search. If elements from array 2 are located in array 1, print them. In the end, print all of the remaining elements from array 1.

Algorithm

  • Let A[] have a size of m and B[] have a size of n.
  • Copy the contents of A[] to a temporary array of size m called temp.
  • Create a new array called visited[] and set all of its entries to false. The array visited[] is used to indicate which elements in temp[] are copied to A[].
  • Sort by temp[].
  • Set the output index ind to zero.
  • For each element of B[i] in B[], do the following:
    a. If there are any occurrences of B[i] in temp[], then binary search for all occurrences of B[i] in temp[], copy all occurrences to A[ind], and increment ind. Also, make a note of the copied elements that have been visited[]
    b. Copy all elements from temp[] to A[] that have not been visited.


 A C++ program to sort an array according to the order defined by another array 

Implementation 

#include <bits/stdc++.h>
using namespace std;

int first(int arr[], int start, int end, int x, int n)
{
  if (end >= start) 
     {
         int middle = start + (end - start) / 2;
  
         if ((middle == 0 || x > arr[middle - 1]) && arr[middle] == x)
         return middle;

         if (x > arr[middle])
         return first(arr, (middle + 1), end, x, n);

         return first(arr, start, (middle - 1), x, n);
    }
  return -1;
}
   
void sortAccording(int A[], int B[], int m, int n)
{
      int temp[m], visited[m];
      for (int i = 0; i < m; i++) 
     {
      temp[i] = A[i];
      visited[i] = 0;
     }
  
      sort(temp, temp + m);
      int ind = 0;
      for (int i = 0; i < n; i++) 
  {
      int f = first(temp, 0, m - 1, B[i], m);
      if (f == -1)
      continue;
  
      for (int j = f; (j < m && temp[j] == B[i]); j++)
    {
      A[ind++] = temp[j];
      visited[j] = 1;
    }

  }
     for (int i = 0; i < m; i++)
     if (visited[i] == 0)
     A[ind++] = temp[i];
}

     void printArray(int arr[], int n)
  {
     for (int i = 0; i < n; i++)
     cout << arr[i] << " ";
     cout << endl;
  }

//Main function of the program
   int main()
{
   int A[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };
   int B[] = { 2, 1, 8, 3 };
   int m = sizeof(A) / sizeof(A[0]);
   int n = sizeof(B) / sizeof(B[0]);
   cout << "Your sorted array is \n";
   sortAccording(A, B, m, n);
   printArray(A, m);
   return 0;
}

 

Output

Your sorted array is 
2 2 1 1 8 8 3 5 6 7 9 

Complexity Analysis:

Time Complexity: 
The Sorting Algorithm takes O(M * log M) time to complete.
O(N log M) time is required for the combined operation of binary search along with copying and remembering the copied elements.
As a result, the overall complexity is O(M Log M + N log M).

Space Complexity: 
The space complexity of the above algorithm is O(n). Since we are using a temporary array to copy the elements of our given array. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2

Make Use of Hashing

The goal is to keep track of the frequency of each element of the first array in a hash table.

Algorithm

  • Check whether or not each element of the second array is present on the map.
  • Print the element n times if it appears on the map, where n is the frequency of that element in the first array.
  • We also remove that element from the map, leaving only the elements in the first array that are present (but not present in the second array).
  • They must be sorted before being added at the end.
  • Although keys in std::map or TreeMap are already ordered, the insertion and retrieval times are O(log(n)).
  • We get O(1) insertion and retrieval time if we use std::unordered map or HashMap, but we'll have to sort because the keys aren't in any particular order.


The following is how the above strategy is put into action:

Implementation C++

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
void hashingSort(int first[], int second[], int p, int q)

{
unordered_map<int, int> freq;  
for (int i = 0; i < p; i++) 
   {
    freq[first[i]]++;
   }

   int index = 0;
   for (int i = 0; i < q; i++)
   {
      while (freq[second[i]])
   {
      first[index++] = second[i];
      freq[second[i]]--;
   }   
      freq.erase(second[i]);
   }    

int i = index;
for (auto it = freq.begin(); it != freq.end(); it++)
    {
       while (it->second--) 
      {
        first[index++] = (it->first);
      }
    }
     sort(first + i, first + index);
}

void printArray(int arr[], int q)
   {
     for (int i = 0; i < q; i++) 
   {
     cout << arr[i] << " ";
   }
     cout << endl;
   } 

//Main Function of the program
int main()
{
int first[] = { 5, 8, 9, 3, 5, 7, 1, 3, 4, 9, 3, 5, 1, 8, 4 };
int second[] = { 3, 5, 7, 2 };
int p = sizeof(first) / sizeof(first[0]);
int q = sizeof(second) / sizeof(second[0]);
hashingSort(first, second, p, q);
cout << "The array after being sorted through hashing is ";
printArray(first, p);
return 0;
}

 

Output

The array after being sorted through hashing is 3 3 3 5 5 5 7 1 1 4 4 8 8 9 9 

Complexity
 

Time complexity: 
The above solution has an O(mlog(m) + n) time complexity, where m and n are the total number of elements in the first and second arrays, respectively.

Under the assumption that the hashing function takes O(log(n)) insertion and retrieval time, checking each element in the second array and printing all elements that appear in the hashmap on average O(m+n) time.

Space Complexity: O(n), with the increase in the number of entries the size of the hashmap increases linearly.
 

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What is a relative order array, and how does it work?

Programming. Assume we have two arrays, arr1 and arr2, each with its own set of elements, and all of the elements in arr2 are also present in arr1. We must sort the elements of arr1 so that the relative ordering of items in arr1 matches the relative sequence of items in arr2.

How should two arrays be sorted in the same order?

  • Make a list of the main array's indexes (sortableArray)
  • Using a custom comparison, sort the indexes.
  • The index is used to look up the function that compares the values.
  • Map each index to its value for each input array.

How do you combine two arrays in the most efficient way?

We calculate their length and store it in the fal and sal variables to merge two arrays. We create a new integer array result that holds the sum of both arrays' lengths. Using the arraycopy() function, copy each element of both arrays to the result array.

Can you think of a way to combine two separately sorted arrays into a single sorted array?

Make an array of size n1 + n2 called arr3[].Traverse arr1[] and arr2[] at the same time. Pick the smallest of the current elements in arr1[] and arr2[], copy it to the next position in arr3[], and move forward in arr3[] and the array whose element is picked.

Conclusion

As discussed in this article, the problem "Sort an array according to the order defined by another array" asks you to sort the first array according to the second array so that the numbers in the first array are sorted relative to all of the values in the arr2[] array. We use Hash Ordered Map to get the desired result.

We hope that this article has helped you enhance your knowledge regarding the subject of Array and relative sorting.

After reading about the sorting of arrays, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about array sorting algorithms, maximum sum such that no two elements are adjacent, and Finding maximum repeating number in an array  Also see time complexity and Complexity Analysis.

You can also practice some relevant problems at Coding Ninjas Studio such as:

  1. Sum of the infinite array
  2. Maximum Subarray Sum
  3. First missing positive
  4. Aggressive Cows
  5. K largest element and many more.
     

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

 

Previous article
Find The Last
Next article
Sort Elements by Frequency
Live masterclass