What if you are given an array of 1000 elements and you are asked to sort the array? What would be your first step?
Most of you would say: “deciding the method to sort the elements”.
Think again and think like a programmer!
Again, What would you do?
Certainly, some of you have guessed it right this time! You will check how much data is already sorted!!
Well, that’s what inversion count in an array does while sorting elements.
Inversion count in an array depicts how far the array is from being sorted. If the given array is already sorted, the inversion count returns 0 and if the given array is sorted in the reverse order, the count of inversions will be maximum.
With that said, if you are wondering how to find inversion counts, this post can help you.
Here we are going to discuss how you can find the count of inversions using merge sort and other methods.
Understand The Problem Statement
For the given array, if array[i] > array[j] and i<j, then this pair (i,j) is called an inversion of an array. You are required to write the code to count the total inversions present in the given array.
Let’s consider the following example to understand the problem statement better.
You are given the following array:
A={ 3, 2, 1}
The output of the array will be 3
In the following input, the following inversions can be found:
(3,2), (2,1), and (3,1).
How To Find Inversion Count Using Merge Sort?
One of the methods to count inversions in an array, merge sort is used. In this method, the divide and conquer approach is followed.
First, the given array will be divided into two equal halves. The total count of inversions will be found by adding the inversions found in both halves. At the time of merging the array, the count will be calculated by comparing items of both halves.
In this approach, two pointers are used that will compare the index of the array on both sides.
What If You Still Find Inversion At The Time Of Merge?
At the time of the merge process, use i for indexing the left subarray. Also, use j for indexing the right subarray. In the case while sorting, you find a[i] to be larger than a[j], there will be (mid-1) inversions in the array.
This is because the right and left subarrays are already sorted. Therefore, the elements present in the left sub-array will be greater than in the right one.
Algorithm
By now you must have an idea of how inversions can be found in an array using merge sort. Here is the complete algorithm that you need to follow while writing the code to find the count of inversions.
- To begin with, you will have to divide the given array into equal halves recursively.
- This process will continue until only one element is left at the end which can not be further divided.
- After this, you need to count the inversions present in the second and first half. Also, calculate the count of inversions in the merge process as well.
- To find the inversions while merging, you need to maintain two pointers: j and i. Here, pointer i will point to the beginning element of the left side and j will point to the beginning element of the right side. Elements at both locations will be now compared.
- In case you find that the jth element is larger than the ith element, add the element to the sorted list. Otherwise, increase the count by mid-1.
Complexity Analysis Of The Method
When choosing an algorithm to resolve a certain problem, you need to know the time and space required to complete the process. Here, we have discussed the space and time complexity of this method:
- Space Complexity: The space complexity of this method is O(n). This requires a temporary array for the process.
- Time Complexity: The time complexity of this method is O(nlogn). This is because, at each level, the array is completely traversed. The total number of levels is log n. So, the process will be done for O(n logn) times.
One thing that you have to note is that this code will modify the given array. In case you wish to count inversions only, you will have to make a copy of the given array and then call the mergesort() function. It will keep the original order of the array the same.
Other Methods To Find Inversion Count In An Array
Although it is preferred to use merge sort to count inversions in an array, there are other methods as well that you can use. Below we have discussed the methods to find conversion count in an array.
Bisection And Heapsort
- In this method, you will have to make a heap and add a new pair of elements.
- Post sorting all the elements, you need to pop out the minimum element and then create a list of new sorted elements with indexes.
- Now, check the differences between the original and bisection indexes of the newly created list.
- Add the difference.
The Basic Approach
You are required to traverse the complete array. For each index, find the count of the smallest element on the right side of the given array. You can use a nested loop to traverse the array. Now, you will have to add the count of the index in the array. Finally, return the sum. This process is a very basic process and may take more time to count the inversions.
Winding Up
It is certainly a good option to check how far the array is from being sorted using inversion count. This will make it easier for you to sort the elements of the array. Merge sort is one of the efficient methods to count inversions in an array.
Moreover, this question is usually asked in the Amazon interview experience along with questions like the longest palindromic subsequence.
The post provides you with all the feasible and possible solutions to count the inversions. So, before going for an interview, you must check out this problem if you wish to stand out from the crowd.