2. Inversions. Let A[1..n] be an array of n distinct numbers. If i < j and A[i]
ID: 3883297 • Letter: 2
Question
2. Inversions. Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
(a) List the five inversions of the array < 2, 3, 8, 6, 1 >.
(b) What array with elements from the set {1, 2, . . . , n} has the most number of inversions? How many does it have?
(c) What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
(d) Give an algorithm that determines the number of inversions in any permutation of n elements in O(n log n) worst-case running time. (Hint: Modify Merge-sort.)
Explanation / Answer
Solution:
a)
The definition of an inversion is as follows: Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
The five inversions of the array < 2, 3, 8, 6, 1 > are as follows:
(2, 1), (3,1), (8, 6), (8, 1) and (6, 1)
b)
The n-element array with most inversions is <n, n-1,..2,1> because it will be the reverse sorted array. The number of inversions are as follows: (n-1) + (n-2) + (n-3) +…+2+1 = n(n-1)/2.
c)
The code for the insertion sort is as follows:
for j= 2 to length(A).
do key = A[j]
i = j-1
while i>0 and A[i]>A[i+1]
do A[i+1] = A[i]
i = i-1
A[i+1] = key
Here, the invariant is maintained such that the first k elements of the array A are already sorted and then element A[k+1] is inserted into the correct place. Thus, the running time of the insertion sort is a constant time the number of inversions. Let the inversion be denoted by X(i) such that A[j]>A[i], then the number of inversions in the array A will be summation of all inversions. If the array is sorted, there will be no inversions, so the running time of insertion sort will be proportional to the number of inversions in the array A.
d)
An algorithm that determines the number of inversions in any permutation on n elements in O(nlogn) worst case time is as follows:
//initialise inversions to 0.
int inversions = 0
//The mergeSort algorithm.
int[] mergeSort (int[] a)
//if the length of the array is less than 1, return the array.
if a.length <= 1
return a
//take a variable mid, store the half of the array in it.
int mid = a.length / 2
int[] left = new int[mid]
//Now, store the elements from first position till mid, the left
//array.
for (int i=0;i<mid;i++)
left[i] = a[i]
//Store the rest of the elements in the right array.
int[] right <-new int[a.length - mid]
for (int i = mid; i < a.length; i++)
right[i - mid] = a[i]
left = mergeSort(left)
right = mergeSort(right)
return merge(left, right)
//The merge algorithm.
int[] merge(int[] l, int[] r)
int[] a = new int[l.length + r.length]
int lIndex = 0
int rIndex = 0
int i = 0
while lIndex < l.length && rIndex < r.length
do
if (l[lIndex] <= r[rIndex]) then
a[i++] = l[lIndex++]
else
inversions <-inversions + l.length - lIndex
a[i++] = r[rIndex++]
while lIndex < l.length
do
a[i++] = l[lIndex++]
while rIndex < r.length
do
a[i++] = r[rIndex++]
return a
This algorithm will determine the number of inversions in any permutation of n elements in O (n logn) worst case.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.