CODEWITHSUNDEEP
algorithm
LeafGlowPath
LeafGlowPath

Reputation: 3799

Count inversions with merge-sort

I am reading "Introduction of Algorithm, 2nd edition". It has an exercise, Problem 2.4

Let A[1 n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(n lg n) worst-case time. (Hint: Modify merge sort.)

Then I found this solution in the Instructor's Manual

COUNT-INVERSIONS ( A, p, r)
inversions ← 0
if p < r
  then q ← ( p + r)/2
   inversions ← inversions +C OUNT-I NVERSIONS ( A, p, q)
   inversions ← inversions +C OUNT-I NVERSIONS ( A, q + 1, r)
   inversions ← inversions +M ERGE -I NVERSIONS ( A, p, q, r)
return inversions


MERGE -INVERSIONS ( A, p, q, r)
n1 ← q − p + 1
n2 ← r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
  do L[i] ← A[ p + i − 1]
for j ← 1 to n2
  do R[ j ] ← A[q + j ]
L[n 1 + 1] ← ∞
R[n 2 + 1] ← ∞
i ←1
j ←1
inversions ← 0
counted ← FALSE
for k ← p to r
  do 
  if counted = FALSE and R[ j ] < L[i]
    then inversions ← inversions +n1 − i + 1
    counted ← TRUE
  if L[i] ≤ R[ j ]
    then A[k] ← L[i]
    i ←i +1
  else A[k] ← R[ j ]
    j ← j +1
    counted ← FALSE
  return inversions

My question is, I found the variable counted really useless. In the first if clause, it might be set to TRUE, but that means R[J] < L[i], so in the last else clause, it's going to be set back to FALSE.

Could anyone give me an example that could explain why counted is needed?

Upvotes: 6

Views: 6133

Answers (1)

interjay
interjay

Reputation: 110155

You're right, the counted variable is useless, since it will always be false when it's tested.

It looks like the author's intention was to avoid counting the same R[j] element twice. But they didn't notice that after counting R[j], j will always be incremented due to going into the else clause, so there's no need for the precaution.

Upvotes: 3

Related Questions