How to Count Inversions using program in Python

In this blog, today we’ll try to count the number of inversions in an array in Python.

Generally, There are many ways to count the number of inversion pairs in an array but In this blog, we will only be seeing two of those methods:

1. Brute Force
2. Merge Sort(Enhanced)

What do we mean by an inversion pair?

An inversion pair is found in an array when two elements Arr[i] and Arr[j] satisfy the relation:

• Arr[i] > Arr[j]
•     i    <    j

These pairs are really useful in predicting how close an array is to being fully sorted. If an array is sorted, then there are no inversion pairs in the array as none of the pairs would satisfy the given criteria. If an array is reversely sorted then every pair which satisfies the given criteria is an inversion pair.

Ex:

arr[] = {22 , 42 , 37}

Here the only inversion pair is:
{42,37}  as index 1 < index 2  but arr[index 1]> arr[index 2]

arr[] = {99 , 80 , 23 , 4}

Here this is a reverse sorted array and the inversion pairs are:
{99,80} ; {99,23} ; {99,4} ; {80,23} ; {80,4} ; {23,4} 
with the same reasonings as above

SOLUTIONS

 

1. Brute Force

   ALGORITHM:

   • For the brute force algorithm, we can just traverse the array for every element and find all the elements to the right of this index, which are smaller than the chosen element.
   • Finally, add all these inversion pairs and we get the inversion count.
   • Print the count of inversions

   IMPLEMENTATION:

   def inversion(arr):
   
       #Variable which stores the total number of inversion counts
       inv_count = 0
   
       for i in range(len(arr)):
           #A loop to check all elements to the right of arr[i] 
           for j in range(i,len(arr)):
               #if it turns out to be smaller then increase the inversion count by 1 
               if(arr[j] < arr[i]):
                   inv_count += 1
       
       return inv_count
   
   arr = [99,80,23,4]
   
   print(inversion(arr))

   Output: 
   
   6

   Complexity:  O(n^2) worst case

2.  Merge Sort(Enhanced)

    

   BASIC IDEA:

   So our basic idea in this method would be to use Divide and conquer and our merge sort algorithm logic to find the number of inversions in an array
   Now, we can recursively find the number of inversions in our left and right subarrays. The only cases that are left out are when we are trying to merge these two subarrays.

   How do we find these inversion pairs?

   Let i be the starting index in our left sorted sub-array and j be the starting index of our right sorted subarray,then if at any point in time of the merge process if LeftArr[i] > RightArr[j], then that means all the elements to the right of i would also be greater than the RightArr[j], thus we get mid – i inversions.

   ALGORITHM:

   • So first we try to apply the divide and conquer algorithm and divide the array into 2 halves until the recursion limit or our base case is reached.
   • Then as we come out of the recursion we keep track of the number of inversion pairs in our left and right subarrays which have been counted using our specified merge function.
   • So the answer for our total inversion counts would be inv_count in left subarray + inv_count in right subarray + inv_count which arise due to the merging of the 2 arrays

   IMPLEMENTATION:

   #creating a recursive merge sort function with left and right as parameter
   def mergeSort(arr,left,right):
       mid = 0
       inv_count = 0
       if(left < right):
           mid = (left + right ) // 2
   
           #recursively seeing the inversion pairs on left child
           inv_count += mergeSort(arr,left,mid)
           
           #recursively seeing the inversion pairs on right child
           inv_count += mergeSort(arr,mid+1,right)
   
           #Finding the inversion pairs in merge operation
           inv_count += merge(arr,left,mid,right)
   
       return inv_count
       
   def merge(arr,left,mid,right):
       temp_arr = []
       i = left
       j = mid+1
       inv_count = 0
   
       while(i<=mid and j<=right):
           if(arr[i] <= arr[j]):
               #if arr[i]<=arr[j] then its not an inversion pair
               temp_arr.append(arr[i])
               i+=1
           else:
               #if arr[i]>arr[j] then its an inversion pair and arr[j] is an inversion
               #pair with all the elements from i to end of first subarray(i.e mid)
               temp_arr.append(arr[j])
               inv_count += mid - i + 1
               j+=1
   
       #completeing the array if some elements are left out
       while(i<=mid):
           temp_arr.append(arr[i])
           i+=1
   
       while(j<=right):
           temp_arr.append(arr[j])
           j+=1
   
       #transfering this back to the original array
       for i in range(left,right+1):
           arr[i] = temp_arr[i-left]
   
       return inv_count
   
   
   arr = [99 , 80 , 23 , 4]
   
   print(mergeSort(arr,0,len(arr)-1))
   

   Output:
   6

   Complexity:  O(nlogn) computational time and O(1) space utilization