Inversion Count for an array indicates – how far (or close) the array is from being sorted. If the array is already sorted, then the inversion count is 0, but if the array is sorted in the reverse order, the inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Example:
Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions:
(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).
Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions:
(3, 1), (3, 2)
METHOD (Simple):
Approach: Traverse through the array, and for every index, find the number of smaller elements on its right side of the array. This can be done using a nested loop. Sum up the counts for all index in the array and print the sum.
Algorithm:
- Traverse through the array from start to end
- For every element, find the count of elements smaller than the current number up to that index using another loop.
- Sum up the count of inversion for every index.
- Print the count of inversions.
Implementation:
PHP
<?php // PHP program to Count Inversions // in an array function getInvCount(&$arr, $n) { $inv_count = 0; for ($i = 0; $i < $n - 1; $i++) for ($j = $i + 1; $j < $n; $j++) if ($arr[$i] > $arr[$j]) $inv_count++; return $inv_count; } // Driver Code $arr = array(1, 20, 6, 4, 5 ); $n = sizeof($arr); echo "Number of inversions are ", getInvCount($arr, $n); // This code is contributed by ita_c ?> |
Output:
Number of inversions are 5
Complexity Analysis:
- Time Complexity: O(n^2), Two nested loops are needed to traverse the array from start to end, so the Time complexity is O(n^2)
- Space Complexity:O(1), No extra space is required.
Please refer complete article on Count Inversions in an array | Set 1 (Using Merge Sort) for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
