Counting Inversions - Recursive Algorithm

Question

Now in my lecture notes in a course I'm taking I was given the following pseudo-code to Count Inversions (Using a Recursive Algorithm).

function Count_Inversions(Array)
  if size(A) == 1 then return (A,0)
  L = A[1,2, .... , n/2]
  R = A[n+1, n+2, . , n]

  (sortedL,inv_L) = Count_Inversions(L)
  (sortedR,inv_R) = Count_Inversions(R)

  Inv_LR = sum(FindRanks(L,R))
  return (Merge(L,R),inv_L + inv_R + inv_LR)

Now I feel there is a mistake in this algorithm. Does one really need to count the Left and Right Inversions. When we calculate the Rank at every step won't those inversion be included.

For example I have an array with elements 1,6,8,3,7,4,9,2. Now I keep breaking the array till I get single elements. Then I join them (1,6) (3,8) (4,7) , (2,9) Now I'll find the rank of 1 (Left Array) in 6 (Right Array). I do them for each pair and get 3. That is the number of inversions in this step. I keep doing this. Joining them together and finding the ranks of the left array elements in the right array and adding them.

Plus as the array would be sorted in every step the Count_Inversions(L) and Count_Inversions(R) would equal 0.

String · Accepted Answer · 2015-03-26 23:14:50Z

Perhaps your example can help clarifying this. Here is the sequence of arrays passed to Count_Inversions by the recursive calls it makes:

1: [1,6,8,3,7,4,9,2]
2: [1,6,8,3]                    9: [7,4,9,2]
3: [1,6]       6: [8,3]        10: [7,4]        13: [9,2]
4: [1] 5: [6]  7: [8] 8: [3]   11: [7] 12: [4]  14: [9] 15: [2]

The corresponding return values in the left half are:

2: ([1,3,6,8],0+1+1)
3: ([1,6],0+0+0)       6: ([3,8],0+0+1)        
4: ([1],0) 5: ([6],0)  7: ([8],0) 8: ([3],0)

and for the right half we have:

 9: ([2,4,7,9],1+1+2)
10: ([4,7],0+0+1)        13: ([2,9],0+0+1)
11: ([7],0) 12: ([4],0)  14: ([9],0) 15: ([2],0)

so on the top level we have return values:

1: ([1,2,3,4,6,7,8,9],2+4+6)
2: ([1,3,6,8],2)               9: ([2,4,7,9],4)

so you can see how, although all positive contributions do come from FindRanks calls, they come from different levels in the recursion, and the occurrences of FindRanks calls below the toplevel of the algorithm are all due to calling Count_Inversions on left and right halves to enter into a deeper level.

Also note, the algorithm count inversions of subarrays AS they are sorted, not AFTER they have been sorted!

I hope it makes sense, otherwise ask!

So essentially in the you need to use Count_Inversions(L) and Count_Inversions(R) to go deeper into the algorithm. And when it find the ranks it puts them into variables which just keeps summing them up. — George J. Adams
– George J. Adams, Commented Mar 27, 2015 at 9:18

Stack Exchange Network

Counting Inversions - Recursive Algorithm

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Counting Inversions - Recursive Algorithm

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions