Christie's algorithm
The algorithm is presented in Fig. 8 of Christie's paper [CHR:1996]. pi is the input permutation, and pi-1 is its inverse.
while pi is not sorted do:
1. locate the smallest x such that pix != x
2. find largest value y between x-1 and pi-1(x)
3. perform the block-interchange (x, pi-1(y)+1, pi-1(x), pi-1(y+1))
Performing a block-interchange (i, j, k, l) means interchanging the elements pii...,pij-1 with pik,...,pil-1. In the paper, there is a small mistake: The second index of the block-interchange is given as j=pi-1(y) instead of j=pi-1(y)+1 as above.
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 pix != 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(n2).
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).
As we will see below, the re-computation of the inverse permutation can be avoided completely.
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 pix. 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.
