Question 3: [30 points] Inversions: An important part of sorting, higher the num

Question

Question 3: [30 points] Inversions: An important part of sorting, higher the number of inversions, longer the run time to sort the elements) Given any list of n numbers, there are pairs of numbers as you remember from Discrete Math. nn(n-1) For example, the list (1, 3, 5, 4, 2, 6) contains the following 15 pairs (3. 5) (3,4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6) You may note that 11 of these pairs of numbers are in order Let 4/1M) be an array of n distinct numbers. If i ·407. then the pair ri, j) Is called inversion of A. (Please note that for array A indexing starts from 1) Using the example above indexes (3,4) is an inversion of A because 3rd index in array A contains 5 and 4th index in array A contains 4 and clearly A[31 > A[4] Using this example list 5 inversions of the array A = [2.3.8.6.1], please keep in mind that indexing starts from 1. Remember that inversions are specified by indices rather than by the values in the array a) b) What array with elements from the set (1,2, ...n) has the most inversions? How many does it have? What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer c)

Explanation / Answer

a) Array elements are [2,3,8,6,1]

Inversions : ( 1, 5 ) [because 2 > 1]
                      ( 2, 5 ) [because 3 > 1]
                      ( 3, 4 ) , ( 3, 5 ) [because 8 > 6 and 8> 1]
                     ( 4 , 5 ) [because 6 > 1]

b) {1,2,3,4,5. . .n }

For Index 1 , It will have n-1 Inversion i.e (1,2), (1,3)...(1,n)
For Index 2 , It will have n-2 Inversion (2,3), (2,4)...(2,n)
........
=> Total number of inversion = > n-1 +. n-2 +. n-3 +. .. 1
=> n(n-1)/2

c) The Insertion sort and inversion are oppositely related
So if the Input is Sorted Number of inversion is maximum the complexity of Insertion Sort is minimum


{ 1,2,3,4,5. . .n } = > Inversion is N2 , Insertion Sort takes N time

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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