Python Program to Sort Array according to the order defined by Another Array

Sort Array according to the order defined by Another Array

In this article, we will learn In this article, we will learn about Python Program to Sort Array according to the order defined by Another Array.

We have given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order. 
Example: 

Input:  A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
        A2[] = {2, 1, 8, 3}
Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}
Sort an array according to the order defined by another array in python

Keypoint

In this section we will learn about basic knowledge which we need to know before coding the above Program. So we must have knowledge of what is an array? 

What is an array?
An array is a data structure, it is collection of similar data elements which is stored at contiguous memory locations in which each data element can be accessed directly by only using its index number.
 
About Python language:-
Python is a popular programming language. Python is a high level language that will make a programmer focus on what to do instead of how to do.
Its design philosophy emphasizes code readability with its use of significant indentation. Its language constructs as well as its object-oriented approach aim to help programmers write clear, logical code for small and large-scale 
 
 
How to declare an array?
To declare an array in C,a programmer specifies the type of the elements and the number of elements required by an array as follows − This is called a single-dimensional array. The arraySize must be an integer constant greater than zero and type can be any valid C data type. For example, to declare a 10-element array called balanceof type double, use this statement − Here balanceis a variable array which is sufficient to hold up to 10 double numbers

.

Algorithm :

  • Input both the arrays, arr1 and arr2.
  • Span the elements of arr2 from i=1 lenght(arr2).
  • Binary Search to check if arr1 contains the i^th element of Arr2.
  • Print all the elements.
  • Let’s go to step 2 again and again until all the elements of arr2 have been traversed.
  • If there are any remaining element in arr1, print them.
Sort an array according to the order defined by another array in Python

Code of Python Program to Sort Array according to the order defined by Another Array

"""A Python 3 program to sort an array 

according to the order defined by 

another array"""


def first(arr, low, high, x, n) :

    if (high >= low) :

        mid = low + (high - low) // 2; # (low + high)/2; 

        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

    


def sortAccording(A1, A2, m, n) :

    temp = [0] * m

    visited = [0] * m

    

    for i in range(0, m) :

        temp[i] = A1[i]

        visited[i] = 0


    # Sort elements in temp

    temp.sort()

    

    # for index of output which is sorted A1[]

    ind = 0


    for i in range(0, n) :

        

        # Find index of the first occurrence

        # of A2[i] in temp

        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[]

        j = f

        while (j<m and temp[j]== A2[i]) :

            A1[ind] = temp[j];

            ind = ind + 1

            visited[j] = 1

            j = j + 1

    

    # Now copy all items of temp[] which are

    # not present in A2[]

    for i in range(0, m) :

        if (visited[i] == 0) :

            A1[ind] = temp[i]

            ind = ind + 1

            

# Utility function to print an array

def printArray(arr, n) :

    for i in range(0, n) :

        print(arr[i], end = " ")

    print("")


# Driver program to test above function.

A1 = [2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8]

A2 = [2, 1, 8, 3]

m = len(A1)

n = len(A2)

print("Sorted array is ")

sortAccording(A1, A2, m, n)

printArray(A1, m)
Output :

Sorted array is 
2 2 1 1 8 8 3 5 6 7 9