Q2-Count Inversions [15 Points] Sometimes you are interested in finding how far an array is from...

 

Transcribed Image Text:

Q2-Count Inversions [15 Points] Sometimes you are interested in finding how far an array is from being sorted. This can be found by counting number of inversions in an array. If the array is already sorted, then inversion count is 0. If the array is sorted in reverse order then inversion count is the maximum. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i<j. For example, the sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3) and its inversion count is 3. Write a function CountInversions(1st) that takes an array of positive integers and returns number of inversions in it. You can certainly do this for O(n²) time. Think of a better solution that solves the problem in not more than O(nlogn) time. Q2-Count Inversions [15 Points] Sometimes you are interested in finding how far an array is from being sorted. This can be found by counting number of inversions in an array. If the array is already sorted, then inversion count is 0. If the array is sorted in reverse order then inversion count is the maximum. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i<j. For example, the sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3) and its inversion count is 3. Write a function CountInversions(1st) that takes an array of positive integers and returns number of inversions in it. You can certainly do this for O(n²) time. Think of a better solution that solves the problem in not more than O(nlogn) time.

Answer rating: 100% (QA)

Ans To count the number of inversion of an unsorted array there are various methods out of those methods 1The simple On2 methodIn this method we simpl... View the full answer