Sorting Strings with Three-Way Radix Quicksort

By Jon Bentley and Robert Sedgewick

Dr. Dobb's Journal November 1998

void iqs(int a[], int n) 
{   int le, lt, gt, ge, r, v;
    if (n <= 1)
         return;
    swap(a, 0, rand() % n);
    v = a[0];
    le = lt = 1;
    gt = ge = n-1;
    for (;;) {
        for ( ; lt <= gt && a[lt] <= v; lt++)
            if (a[lt] == v)
                swap(a, le++, lt);
        for ( ; lt <= gt && a[gt] >= v; gt--)
            if (a[gt] == v)
                swap(a, gt, ge--);
        if (lt > gt)
                break;
        swap(a, lt++, gt--);
    }
    r = min(le, lt-le);
    vecswap(a, 0, lt-r, r);
    r = min(ge-gt, n-ge-1);
    vecswap(a, lt, n-r, r);
    iqs(a, lt-le);
    iqs(a + n-(ge-gt), ge-gt); 
} 

Example 1: Three-way quicksort for integer arrays.

Back to Article