I\'m learning divide-and-conquer now, and here below is the Sort-and-Count algor

Question

I'm learning divide-and-conquer now, and here below is the Sort-and-Count algorithm for counting teh inversions which means given a sequence of n numbers a1, . . . , an, which we assume are all distinct, and we define an inversion to be a pair i < j such that ai > aj. . Now if I want to count teh "significant" inversion (i < j and ai > 2aj ), what changes I need to do base on Sort-and-Count algorithm ? why the running time complexity will still be same ?

Sort-and-Count (L) t if list L has one element. return o and the list L Divide the list into two halves A and B AI A) Sort-and-Count (A) (ra, B) Sort-and-Count (B) (r L) Merge-and-count. (A B) return r r, r, r and the sorted list L TOn)

Explanation / Answer

Before explaining any further let me explain to you what exactly an inversion is:

In version count for an array means how far the array is from being sorted. For sorted arrays inversion count is 0, and when the array is is reverse order the inversion count will be maximum.

Now let's com to the point, the given sort-and-count is giving same time complexity irrespective of inversion count is only because it is using merge procedure, and property of merge procedure is that it will break the given array into two halves and and keep on breaking until only one element remains and then it will start to merge the elements in to sorted order. What is happening here is when the array is divided into two array the track of inversion count is lost, and there is no significance remaining of inversion. This algorithm can be modified by maintaining the inversion count in left and right sub array after dividing.

Well, for inversion insertion sort works best and for that generic way is explained below:

or each inversion body of inner loop is iterates only once in insertion sort.. At every i-th iteration, if A[1..i] has min versions with A[i],
they are in A[il..i1] (because sorted elements are there before i). This means that the inner loop will run only l number of times. Because of this process new inversions are not introduced in the every outer loop iteration is resolved in exactly l iteration. Where l is the distance the element is  "pushed towards the front of the array".

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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