Sunday, September 13, 2009

Quicker Quicksort

A lot of we do requires sorting. For years, the best-of-breed was quicksort, perhaps with a randomizer pre-processor to avoid the worst-case scenario of already sorted data. BTW, here is a linear-time randomiser:


function nshuffle(a, i,j,n,tmp) {
n=a[0]; # a has items at 1...n
for(i=1;i<=n;i++) {
j=i+round(rand()*(n-i));
tmp=a[j];
a[j]=a[i];
a[i]=tmp;
};
return n;
}
function round(x) { return int(x + 0.5) }

Now there is empirical evidence that a new quicksort that uses two (not one) pivots is faster:

  • Pick an elements P1, P2, called pivots from the array.
  • Assume that P1 <= P2, otherwise swap it.
  • Reorder the array into three parts: those less than the smaller
    pivot, those larger than the larger pivot, and in between are
    those elements between (or equal to) the two pivots.
  • Recursively sort the sub-arrays.
This new method is up to twice as fast as old quicksort.

No comments:

Post a Comment