Let A = [a 1 , a 2 , . . . , a n ] be a collection of integers. A pair (i, j) is
ID: 3826442 • Letter: L
Question
Let A = [a1, a2, . . . , an] be a collection of integers. A pair (i, j) is called an inversion if i < j but ai > aj . For example, if A = [2, 3, 8, 6, 1] then the list of inversions is (1, 5),(2, 5),(3, 4),(3, 5),(4, 5). Design an algorithm (provide good pseudocode) that, given a collection of integers A outputs a list of its inversions. Provide a complete analysis of your algorithm
Be sure to include the following:
1. Complete pseudocode
2. Identify the input and the input size, n
3. Identify the elementary operation
4. Compute how many times the elementary operation is executed with respect to the input size n
5. Provide a Big-O asymptotic characterization for the algorithm’s complexity
Explanation / Answer
This algorithm is based on Divide and Conquer paradigm.
It is implemented using merge sort.
In this approach the time complexity will be O(n log(n)) .
Actually in divide step we divide the problem in two parts. And then two parts are solved recursively.
The key concept is two count the number of inversion in merge procedure.
In merge procedure we pass two sub-list. The element is sorted and inversion is found as follows :
1) Set count=0,0,i=left,j=mid. C is the sorted list.
2) Traverse list1 and list2 until mid element or right element is encountered .
3) Compare list1[i] and list[j].
i) If list1[i]<=list2[j]
c[k++]=list1[i++]
else
c[k++]=list2[j++]
count = count + mid-i;
4) add rest elements of list1 and list2 in c.
5) copy sorted list c back to original list.
6) return count.
Key concept : If an element of list two is greater than an element of list1 than all the remaining element of list1 are greater than this element. That's why we increment count by mid-i. This recursively sort the list and find the number of inversion.
Complexity is o(nlogn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.