Java program to Sort an array according to the order defined by another array

October 12, 2022

Sort an array according to the order defined by the other array

Here we will learn about Java program to Sort an array according to the order defined by another array which is discussed over here. We are 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 accordingly 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.

Method Discussed :

Method 1 : Using Sorting and Binary searching.
Method 2 : By making customized comparator.

Method 1 :

Declare a temporary array temp of size m and copy the contents of arr1[] to it.
Declare another array visited[] and initialize all entries in it as false. visited[] is used to mark those elements in temp[] which are copied to arr1[].
Sort temp[] using any sorting technique
Declare the output index ind as 0.
Do following for every element of arr2[i] in arr2[]
- Binary search for all occurrences of arr2[i] in temp[], if present then copy all occurrences to arr1[ind] and increment ind. Also mark the copied elements visited[]
Copy all unvisited elements from temp[] to arr1[]

Method 1 : Code in Java


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


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

class PrepInsta 
       {

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

            if ((mid == 0 || x > array[mid-1]) &&
                array[m] == x)
                return mid;
            if (x > array[m])
                return first(arr, (m + 1), h,
                             x, n);
            return first(array, l, (m -1), x, n);
        }
        return -1;
    }

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

        int temp[] = new int[m1], visited[] = new int[m1];
        for (int i = 0; i < m1; i++)
        {
            temp[i] = array1[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, m1-1, array2[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 < m1; i++)
            if (visited[i] == 0)
                arr1[ind++] = temp[i];
    }

    // Function to print an array
    static void print_array(int array[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(array[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.l;
        int n = arr2.l;
        System.out.print("The Sorted array : ");
        sort_according(array1, array2, m1, n);
        print_array(arr1, m1);
    }
}

Output:-

4, 4, 2, 2, 2, 1, 3, 3, 5

Determine can all numbers of an array be made equal

Finding Minimum sum of absolute difference of given array

Replace each element of the array by its rank in the array

Finding equilibrium index of an array

Rotation of elements of array- left and right

Method 2 :

In this method we will create our own customized compare method.

Method 2 : Code in Java

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
 
class Main {
 
    static void sortAccording(int[] A1, int[] A2, int m, int n)
    {
        HashMap index = new HashMap<>();
 
        for (int i = 0; i < n; i++) {
            if (!index.containsKey(A2[i]))
                index.put(A2[i], i + 1);
        }
 
        
        int[] tmp= Arrays.stream(A1).boxed().sorted((p1, p2) -> {
                      int idx1 = index.getOrDefault(p1, 0);
                      int idx2 = index.getOrDefault(p2, 0);
 
                      if (idx1 == 0 && idx2 == 0)
                          return p1 - p2;
 
                      if (idx1 == 0)
                          return 1;
 
                      if (idx2 == 0)
                          return -1;
 
                      return idx1 - idx2;
                  }).mapToInt(i -> i).toArray();
 
        // Sorted values are copied to the original
        // array
        for (int i = 0; i < m; i++) {
            A1[i] = tmp[i];
        }
    }
 
    // Driver program to test the above function
    public static void main(String[] args)
    {
        int arr1[] = { 20, 1, 20, 5, 7, 1, 9, 39, 6, 18, 18 };
        int arr2[] =  { 20, 1, 18, 39 };
        int m = arr1.length;
        int n = arr2.length;
        sortAccording(arr1, arr2, m, n);
        System.out.println(Arrays.toString(arr1));
    }
}

Output:-

[20, 20, 1, 1, 18, 18, 39, 5, 6, 7, 9]

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

7 comments on “Java program to Sort an array according to the order defined by another array”

NAZIA KHAN
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 3, 2, 4, 2, 5};
int b[] = {4, 2, 1, 3};boolean v[]=new boolean[a.length]; Arrays.fill(v,false);
for(int i=0;i<b.length;i++){
for(int j=0;j<a.length;j++){
if(b[i]==a[j]){
System.out.print(a[j]+" ");
v[j]=true;
}
}

}
for(int j=0;j<v.length;j++){
if(v[j]==false){
System.out.print(a[j]+" ");
}
}
}

0

Log in to Reply
manicampusplacements
import java.io.*;
import java.util.Arrays;

class Main
{

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

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

// Sort according to the order defined by array 2
static void sort_according(int array1[], int array2[], int m1,
int n)
{

int temp[] = new int[m1], visited[] = new int[m1];
for (int i = 0; i < m1; i++)
{
temp[i] = array1[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, m1-1, array2[i], m1);

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

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

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

// Function to print an array
static void print_array(int array[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(array[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);
}
}

0

Log in to Reply
Bishal
import java.util.*;
public class Program
{
public static void main (String[] args)

{
int a[]={1,2,3,4,3,2,4,2,5};
int b[]={4,2,1,3};
int i;
int j;
//int n=a.length;
//int m=b.length;

for( i=0;i<b.length;i++){
int count=0;
for( j=0;j0){
System.out.print(b[i]+” “);
}
}
for ( i = 0; i < a.length; i++)
{

for (j = 0; j < b.length; j++)
if (a[i] == b[j])
break;

if (j == b.length)
System.out.print(a[i] + " ");
}

}
}

0

Log in to Reply
Prithuraj
int arr1[] = { 1, 2, 3, 4, 3, 2, 4, 2, 5 };
int arr2[] = { 4, 2, 1, 3 };
int temp = 0;
int ptr = 0;
for (int i = 0; i < arr2.length; i++) {
for (int j = 0; j < arr1.length; j++) {
if (arr2[i] == arr1[j]) {
temp = arr1[ptr];
arr1[ptr] = arr1[j];
arr1[j] = temp;
ptr++;
}
}
}
System.out.println(Arrays.toString(arr1));

6

Log in to Reply
santhosh
// for index of output which is sorted A1[]
int ind = 0;

// Consider all elements of A2[], find them in temp[]
// and copy to A1[] in order.
for (int i = 0; i < n; i++) {
// Find index of the first occurrence of A2[i] in temp
int f = first(temp, 0, m – 1, A2[i], m);

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

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

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

// Utility function to print an array
void printArray(int arr[], int n)
{

// Iterate in the array
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

// Driver Code
int main()
{
int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };
int A2[] = { 2, 1, 8, 3 };
int m = sizeof(A1) / sizeof(A1[0]);
int n = sizeof(A2) / sizeof(A2[0]);

// Prints the sorted array
cout << "Sorted array is \n";
sortAccording(A1, A2, m, n);
printArray(A1, m);
return 0;

1

Log in to Reply
DHANANJAY
——CODE IN PYTHON———-
def sort_by_order(n,m):
arr = []
for i in m:
for j in n:
if(i==j):
arr.append(i)
remaining = list(set(n) – set(arr))
for i in remaining:
arr.append(i)
return arr

n = list(map(int,input().split()))
m = list(map(int,input().split()))
print(sort_by_order(n,m))

1

Log in to Reply

DHANANJAY
——Edited Code——
def sort_by_order(n,m):
arr = []
for i in m:
for j in n:
if(i==j):
arr.append(i)
remaining = list(set(n) – set(arr))
for i in remaining:
arr.append(i)
return arr
n = list(map(int,input().split()))
m = list(map(int,input().split()))
print(sort_by_order(n,m))

1

Log in to Reply