Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

ID: 3790926 • Letter: L

Question

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of A if i A[j]. The inversion number of A, denoted by inversion(A), is the total number of inversions of array A. Express the running time of sorting A using insertion sort. Your answer should use asymptotic notations involving n and inversion(A). Justify your answer. List all the inversions of the following array. Suppose you have an array A with n elements. Array D is obtained from array A by deleting two elements and inserting them back (to some positions) in array A. Find an upper-bound on |inversion(A) - inversion(B)|.

Explanation / Answer

1) Running time of insertion sort:

Total number of inversion in an array denotes how far an array is from getting sorted. So, to count number of inversions as in insertion sort, we go to each element of array and find number of elements to its right which are smaller than current element. So basicaly we are calculating inversion(A) n times. And in worst case calculating inversion takes O(n) time.

So time complexity of insertion sort = O(n*inversion(A)) = O(n^2).

2) List Of All inversions in given array:

Inversions for i = 1
( 9 , 8 )
Inversions for i = 1
( 9 , 7 )
Inversions for i = 1
( 9 , 3 )
Inversions for i = 1
( 9 , 4 )
Inversions for i = 1
( 9 , 5 )
Inversions for i = 2
( 8 , 7 )
Inversions for i = 2
( 8 , 3 )
Inversions for i = 2
( 8 , 4 )
Inversions for i = 2
( 8 , 5 )
Inversions for i = 3
( 7 , 3 )
Inversions for i = 3
( 7 , 4 )
Inversions for i = 3
( 7 , 5 )

Python code to find inversions:

A = [9,8,7,3,4,5]
for i in range(0,len(A)):
   for j in range(i+1,len(A)):
       print "Inversions for i = ", i+1
       if(A[i]>A[j]):
           print "( ", A[i], ",", A[j],")"

3) Upper bound:

For an array of n elements, max number of inversions is when array is sorted in opposite order= n(n-1)/2. e.g [6,5,4,3,2,1]

So for reducing the number of inversions most, we will place last two elements at start of the array.

i.e [1,2,3,4,5,6]

So here number of inversions = (n-2)(n-3)/2

So, upper bound on |inversion(A) - inversion(B)| = [n(n-1)/2] - (n-2)(n-3)/2 = (4n-6)/2

Navigate

Let A[1..n] be an array of integers, where n 1. Write an algorithm using pseudoc

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

Question

Explanation / Answer

Related Questions

Navigate