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.

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.

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


#include <iostream>
#include <algorithm>

using namespace std;

// Binary search
int first(int arr[], int low, int high, int x, int n)
{
if (high >= low)
{
int mid = low + (high-low)/2; /* (low + high)/2; */
if ((mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
return first(arr, low, (mid -1), x, n);
}
return -1;
}

// Sort according to the second array’s order
void sort_according(int arr1[], int arr2[], int m, int n)
{

int temp[m], visited[m];
for (int i=0; i<m; i++)
{
temp[i] = arr1[i];
visited[i] = 0;
}

// Sort elements
sort(temp, temp + m);

int ind = 0;

for (int i=0; i<n; i++)
{
// Find index of the first occurrence of arr2[i] in temp
int f = first(temp, 0, m-1, arr2[i], m);

// If not present, no need to proceed
if (f == -1) continue;

// Copy all occurrences of arr2[i] to arr1[]
for (int j = f; (j<m && temp[j]==arr2[i]); j++)
{
arr1[ind++] = temp[j];
visited[j] = 1;
}
}

// Now copy all items of temp[] which are not present in arr2[]
for (int i=0; i<m; i++)
if (visited[i] == 0)
arr1[ind++] = temp[i];
}

// Function to print an array
void print_array(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << ” “;
cout << endl;
}

int main()
{
int m,n;
cout << “\nEnter the size of array 1 : “;
cin >> m;
cout << “\nEnter the size of array 2 : “;
cin >> n;
int arr1[m];
cout << “\nInput the array 1 elements : “;
int i;
for(i = 0; i < m; i++)
cin >> arr1[i];

int arr2[n];
cout << “\nInput the array 2 elements : “;
for(i = 0; i < n; i++)
{
cin >> arr2[i];
}
cout << “\nThe Sorted array : “;
sort_according(arr1, arr2, m, n);
print_array(arr1, m);
cout << endl;
return 0;
}

// Java program to sort an array according to the order defined by another array


import java.io.*;
import java.util.Arrays;

class Main {

// Binary search
static int first(int arr[], int low, int high,
int x, int n)
{
if (high >= low)
{
int mid = low + (high-low)/2;

if ((mid == 0 || x > arr[mid-1]) &&
arr[mid] == x)
return mid;
if (x > arr[mid])
return first(arr, (mid + 1), high,
x, n);
return first(arr, low, (mid -1), x, n);
}
return -1;
}

// Sort according to the order defined by array 2
static void sort_according(int arr1[], int arr2[], int m,
int n)
{

int temp[] = new int[m], visited[] = new int[m];
for (int i = 0; i < m; i++)
{
temp[i] = arr1[i];
visited[i] = 0;
}

// Sort elements in temp
Arrays.sort(temp);
int ind = 0;

for (int i = 0; i < n; i++)
{

int f = first(temp, 0, m-1, arr2[i], m);

// If not present, no need to proceed
if (f == -1) continue;

// Copy all occurrences of arr2[i] to arr1[]
for (int j = f; (j < m && temp[j] == arr2[i]);
j++)
{
arr1[ind++] = temp[j];
visited[j] = 1;
}
}

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

// Function to print an array
static void print_array(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + ” “);
System.out.println();
}

public static void main(String args[])
{
int arr1[] = {1, 2, 3, 4, 3, 2, 4, 2, 5};
int arr2[] = {4, 2, 1, 3};
int m = arr1.length;
int n = arr2.length;
System.out.print(“The Sorted array : “);
sort_according(arr1, arr2, m, n);
print_array(arr1, m);
}
}

# Python program to sort an array according to the order defined by array 2

def first(arr, low, high, x, n) :
if (high >= low) :
mid = low + (high – low)
if ((mid == 0 or x > arr[mid-1]) and arr[mid] == x) :
return mid
if (x > arr[mid]) :
return first(arr, (mid + 1), high, x, n)
return first(arr, low, (mid -1), x, n)

return -1

# sort according to the order defined by array 2
def sortAccording(arr1, arr2, m, n) :
temp = [0] * m
visited = [0] * m

for i in range(0, m) :
temp[i] = arr1[i]
visited[i] = 0

# Sort elements in temp
temp.sort()
ind = 0

for i in range(0,n) :

f = first(temp, 0, m-1, arr2[i], m)

if (f == -1) :
continue

# Copy all occurrences of arr2[i] to arr1[]
j = f
while (jarr1[ind] = temp[j];
ind=ind+1
visited[j] = 1
j = j + 1

for i in range(0, m) :
if (visited[i] == 0) :
arr1[ind] = temp[i]
ind = ind + 1

# Function to print an array
def printArray(arr, n) :
for i in range(0, n) :
print(arr[i], end = ” “)
print(“”)

arr1 = [1, 2, 3, 4, 3, 2, 4, 2, 5]
arr2 = [4, 2, 1, 3]
m = len(arr1)
n = len(arr2)
print(“Sorted array is “)
sortAccording(arr1, arr2, m, n)
printArray(arr1, m)

Time complexity: O(mLogm + nLogm)

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.

// C++ program to sort an array according to the order specified by another array using hashing

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

void customSort(int arr1[], int arr2[], int m, int n)
{
// map to store frequency of each element of first array
unordered_map<int, int> freq;

for (int i = 0; i < m; i++)
freq[arr1[i]]++;

int index = 0;
// do for every element of second array
for (int i = 0; i < n; i++)
{
// If current element is present in the map, print it n times
while (freq[arr2[i]])
{
arr1[index++] = arr2[i];
freq[arr2[i]]–;
}
// delete the element from map
freq.erase(arr2[i]);
}

// sort the remaining elements present in the map
int i = index;
for (auto it = freq.begin(); it != freq.end(); ++it)
while (it->second–)
arr1[index++] = (it->first);

// sort the remaining elements
sort(arr1 + i, arr1 + index);
}

// main function
int main()
{
int arr1[] = { 1, 2, 3, 4, 3, 1, 2, 5, 7};
int arr2[] = { 3, 2, 4, 1};

int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);

customSort(arr1, arr2, m, n);

cout << “After sorting the array is : “;
for (int i = 0; i < m; i++)
cout << arr1[i] << ” “;
cout << endl;

return 0;
}

Output:

sort an array in a relative order specified by another array

Time complexity: O(mlogm + n)