Saturday, March 27, 2010

Number of inversions

Given an array A[0,.... n] of integer an inversion is defined as i < j and A[j] < A[i]. Suppose to randomly permute A. Give an algorithm that computes the number of inversion in A.


  1. I think you got the question wrong. i A[j]. This actually is an inversion isn't it?

  2. I can think of an algorithm whose expected/average run time is O(n lg n). Idea is that of an augment tree data structure to hold the "right tree height" of a node at any point (assuming you are putting elements with values greater than itself to the right of the Node). Now, you simply start walking thru' the array and inserting elements into the tree. If you traverse to the left of the Node, increment the "inversion counter" by that Nodes' right tree height +1 (idea is all nodes to the right of the tree were *inserted* before the current node and are greater than this node). At the end of the insertion, the count will contain the inversion index. This runs in O(n log n) average case.

  3. Do an insertion sort, moving elements to the left, e.g.
    Every time you move an element to the left, there _was_ an inversion.

    So: the number of inversions is the number of time you displaced the elements during insertion sort.