Sorting by Block-Interchanges – Implementation

Christie's algorithm

The algorithm is presented in Fig. 8 of Christie's paper [Christie 1996]. pi is the input permutation, and pi^-1 is its inverse.

A simple implementation

This is almost actual code, and you can find the full version by looking at the HTML source code of the Interactive Sorting page. It implements the original (slow) version of the algorithm.

function sortByBlockInterchanges(permutation) {
  var inverse = [];
  var n = permutation.length;

  for (var i = 0; i < n; ++i) {
    inverse[permutation[i]] = i;
  }
  for (var i = 0; i < n; ++i) {
    if (permutation[i] == i)
      continue; // this position is already sorted

    var y = permutation.max_element(i, inverse[i]);

    permutation = permutation.block_interchange(
      i, inverse[y] + 1, inverse[i], inverse[y + 1]);

    // update inverse
    for (var k = i; k < n; ++k) {
      inverse[permutation[k]] = k;
    }
  }
}

Analysis

The algorithm goes over each element of the permutation. If the element at the current position is not as it should be (this is “the smallest x such that pi_x != x”), the correct indices for a block-interchange are determined and finally the block-interchange is made. Since determining the maximum, doing the block-interchange, and updating the inverse take time O(n), the total runtime is O(n²).

Improvements

We cannot get around looking at each element in turn to see if it is in the correct position, we will therefore leave the outer loop untouched.

To improve the inner loop, we must

• get the maximum element of an interval in time faster than O(n),
• do a block-interchange in time faster than O(n), and
• update the inverse in time faster than O(n).

Inverse permutation

Suprisingly, the algorithm never needs the permutation directly (unless we want to know the indices of the block-interchanges, see below). That is, given x, we never need to determine pi_x. The only operation we actually need is: Given an element of the permutation, what is the next element? Also, we need to know the inverse.

We store the permutation as an array a of nodes. Every node is a triple (previous, next) of indices (or, equivalently, pointers) such that a[i] = (pi(pi^-1(i)-1), pi(pi^-1(i)+1)).

To get the permutation, we start at index i=0 and traverse the next pointers until we are at the last element of the array.

The two needed algorithms, Max-Element and Block-Interchange, can be rewritten to work on nodes instead of regular indices. Block-Interchange is now a constant-time operation since just the next and previous pointers at the borders of the blocks need to be adjusted. Max-Element still needs O(n) time, though.

Maximum element

We store the nodes in a balanced tree to get the time for Max-Element down to O(log n). Each node now has three pointers: parent, left child, and right child. Also, each node contains the maximum value for the subtree of which it is the root. We use an Andersson tree to keep the tree balanced. This means we need another data field which stores the level of a node. (Andersson trees are usually implemented in this way, other methods of keeping the balance information are possible.)

To do the block-interchanges, we implemented merge and split. Merge joins two balanced trees T1 and T2 such that order is maintained. That is, all nodes of T1 are to the left of T2. Also, the resulting tree is balanced. Split is the inverse operation, which splits a tree into parts left and right of a given node. Both operations can be done in O(log n) time. For an actual block-interchange, the tree is split into five parts, which are then merged in the correct order. Thus, a block-interchange can be done in O(log n) time.

Andersson trees

We choose Andersson trees primarily because they are simple to implement. Whereas red/black trees are a special case of B-trees, Andersson trees can be seen as a special case of red/black trees that offers the same worst-case time bounds. In a red/black tree, one of the properties is that a black node may have two red children. In an Andersson tree, the restriction holds that at most the right child of a black node may be red. (One can also say that pseudo nodes in a red/black tree may have size 2, 3 and 4, but only size 2 and 3 in an Andersson tree.)

Further info

Please see the source code of SBBI for more details.