24 Inversions Let A[1 ..n] be an array of n distinct numbers. 1f A[j], then the
ID: 638831 • Letter: 2
Question
24 Inversions Let A[1 ..n] be an array of n distinct numbers. 1f 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 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 On n elements in psi(n lgn) worst-case time. (Hint; Modify merge son.)Explanation / Answer
a)
According to the problem,
The inversion of the given array is always the pair of the indices.
Therefore, the five inversions are:
(1, 5), (2, 5), (3, 5), (3, 4), and (4, 5)
b)
According to the problem, the reverse sorted order of array (n, n 1, ..., 2, 1) is having the most inversions.
The inversions are,
n1 element with the element 1,
n2 element with the element 2, ..., and so on.
Therefore, the number of inversions is the sum:
That is, (n-1)+(n-2)+(n-3)+...+(2)+1=n(n-1)/2
c)
The insertion sort takes ?(n+ f(n)) time, where f(n) is the inversions in the array.
Consider the insertion sort code as shown below:
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
In the above code, the insertion sort maintains an invariant that the first k elements of the array A are already sorted, and then proceeds to insert element A[k + 1] into the correct place.
If there are k0 elements larger than A[k + 1] among the first k elements, this takes ?(k0) time and reduces the number of inversions in the array by k0.
In a sorted array, there are no inversions.
So, the algorithm must use a total of ?(n+ f(n)) time, where the ? (n) term comes from the main loop.
Therefore, the running time of insertion sort is proportional to the number of inversions in A.
d)
the merge sort algorithm is,
int inversions <- 0
int[] mergeSort int[] a
if a.length <= 1
return a
int mid <- a.length / 2
int[] left = new int[mid]
for each i<mid
left[i] = a[i]
int[] right <- new int[a.length - middle]
for each i = mid; i < a.length; i++
right[i - mid] <- a[i]
left <- mergeSort(left)
right <- mergeSort(right)
return merge (left, right)
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.