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.