1
$\begingroup$

How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works?

We assume that the tree data structure we're using is an order statistic tree which means that a) it's a balanced binary tree, b) each node $x$ is augmented with $size$ field which tells us the size of the node's subtree (its inner nodes, including $x$).

We also have an array $L[1..n]$ which contains the values of the keys of the tree (not necessarily sorted).

The algorithm uses two helper functions:

RANK(Tree, node_x) - returns the rank of the key of node_x in array $L$.

SEARCH(Tree, L[i]) - returns the node with the same key as the element $L[i]$ in the given array.

This is the code:

Construct an order statistic tree T for all the elements in L
   t = −|L|
   for i from 0 to |L| − 1 do
      t = t + RANK(T, SEARCH(T, L[i]))
      remove the node corresponding to L[i] from T end for
   return t

If the array is sorted then there're no inversions. Therefore t is incremented each time by $1$ because in sorted array each new element is the minimal one and has rank $1$ (because we delete the last node).

If the array is not sorted then why are we guaranteed that the ranks will at some point "overtake" t and produce the correct amount of inversions?

$\endgroup$
  • 1
    $\begingroup$ Presumably you can prove the correctness of the algorithm by induction. $\endgroup$ – Yuval Filmus Jul 17 '17 at 7:38
  • $\begingroup$ I believe that RANK returns $i \geq 1$ such that node_x is the $i$th smallest element in the tree. $\endgroup$ – Yuval Filmus Jul 17 '17 at 11:14
1
$\begingroup$

At step $i$, the rank of $L[i]$ in $T$ is the number of elements in $L[i],\ldots,L[|L|-1]$ which are at most $L[i]$. Taking into account the $-|L|$ in the beginning, we see that the algorithm counts the number of pairs $i<j$ such that $L[j] \leq L[i]$, which is exactly the number of inversions (assuming all elements are distinct).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.