4. Counting number of inversions. We are given a sequence of n distinct numbers a1,..., an. We define an inversion to be a pair i aj. Give an O(nlogn) algorithm to count the number of inversions. (Hint: Consider modifying Merge Sort to return both the sorted array and the number of inversions. Use recursion to sort and count the inversions of the two halves. Then, during the merging process, count the number of inversions needed for the current recursive step.)
Algorithm: Counting Inversions using Modified Merge Sort
Input: An array of distinct numbers, arr[1...n]
Output: The number of inversions in the array
1. Define a function merge_sort_and_count_inversions(arr):
- If the length of arr is less than or equal to 1, return arr and 0.
- Calculate mid as the integer division of the length of arr by 2.
- Recursively call merge_sort_and_count_inversions on the left half of arr and store the sorted array and inversion count in left_half and left_count.
- Recursively call merge_sort_and_count_inversions on the right half of arr and store the sorted array and inversion count in right_half and right_count.
- Call merge_and_count_inversions with left_half and right_half and store the sorted array and merge_count.
- Return the sorted array and the sum of left_count, right_count, and merge_count.
2. Define a function merge_and_count_inversions(left, right):
- Initialize an empty list merged[] and set inversions to 0.
- Initialize two pointers i and j to 0.
- While i is less than the length of left and j is less than the length of right:
- If left[i] is less than or equal to right[j], append left[i] to merged and increment i by 1.
- Else, append right[j] to merged, increment j by 1, and add (length of left - i) to inversions.
- Extend merged with the remaining elements of left and right.
- Return merged and inversions.
3. Define a function count_inversions(arr):
- Call merge_sort_and_count_inversions on arr and discard the sorted array, keeping only the inversions count.
- Return the inversions count.
4. Get user input for the array as a space-separated string.
5. Split the input string to obtain the array of integers.
6. Call count_inversions with the input array.
7. Print the number of inversions.
8. End.
Step by step
Solved in 3 steps with 1 images
