Counting Inversions with JavaScript
Counting inversions is an easy concept to understand and is based on merge sort. You don’t really need to understand merge sort before going further, I have got that covered.Let’s get into it!!
Counting inversion is the order of sorting, it tells us how much the array is sorted or needs to be sorted. If the inversions are high this could mean that array is not sorted at all or it is sorted in descending order.
Consider the example below-
Here an inversion occurs if index is increasing but element values are decreasing.Consider 50, it is greater than 20,5,30,15,11,18 and its index is smaller than these elements so total inversions for 50 is 6. Same will be performed for all the remaining elements. Total inversions in array obtained is 18.
There are two approaches to solve this problem. Easiest being linear search in which you can run 2 loops over the array and check for above condition. Although it is simple but its time complexity will be O(n²).
Another approach is through enhanced merged sort which is what I’m going to focus on. It is based on Divide and Conquer technique which keeps on dividing the array recursively until some terminating condition is obtained. Time Complexity for this approach is O(nlogn).
First we need to understand how merging takes place in this algorithm.
When the sub array is sorted and inversions are computed then both array and number of inversions are sent back to the function that called it.
As you can see the array is divided until single elements are left which return 0 number of inversions as in case of 50 and 20. These two numbers are then combined together and then merge step takes place as explained above. The total number of inversions are sum of inversions obtained from merge step and from each returned half of the array.
The program returns 18 number of inversions.
That’s it!! It wasn’t that bad,right?? If you would like to see the whole code, you case see here.
Thank you so much for reading everyone.
