Iterative Quicksort: Replacing Recursion with A Stack

mgcadmin 12-04-2022

Quicksort

In my previous post on quick sort I covered in detail the recursive implementation of the famous sorting algorithm. In that post I mentioned that a downside of quick sort is that it has the potential to encounter worst-case quadratic complexity. Performance implication aside, this means that in the worst case the recursive version can reach a very steep stack depth, possibly exhausting the call stack completely. 

void quicksort(int a[], int l, int r) {
    if (r > l) {
        int i = partition(a, l, r);
        quicksort(a, l, i - 1);
        quicksort(a, i + 1, r);
    }
}

One way to avoid this scenario is to replace the call stack with an explicit stack thus removing the recursion all together. Many library implementations of quick sort, including glibc's qsort() do exactly this.

Partitioning Procedure

Quicksort falls into the family of sorting algorithms known as partition exchange sorts. To perform Quicksort you need a partitioning procedure to arrange an array around a pivot element. Partitoning an array should leave all elements less than the pivot falling to its left, and those greater to it's right. 

int partition(int a[], int l, int r) {
    int i = l - 1, j = r, v = a[r];
    for (;;) {
        while (a[++i] < v);
        while (a[--j] > v);
        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a,i,r);
    return i;
}

You can also use Lamuto's algorithm or whichever other partitioning procedure you prefer just keep in mind some of them treat the pivoting element differently and will necessitate altering your code accordingly.

Removing Recursion

Every recursive algorithm has its iterative analog, and Quicksort is no different. As is the case with mergesort, the recursive version of Quicksort has a very simple algorithm which leads alot of developers to not want to tinker with its elegant simplicity. While removing the recursion in mergesort is done via a simple nested loop, with Quicksort it is a bit more involved. because of the way the left and right array bounds are computed we need a way to save them for use in the partitioning function. This is usually handled implicitly by the call stack. A stack data structure is used in it's place instead.

Both Java and C++ have predefined stack data structures as part of their standard libraries. GLIBC uses simple macro definitions to implement a lightweight stack. A stack can be implemented with an array and an integer pointing to the top item yielding a very simple and way to keep track of the array boundaries being sorted. The basic technique then follows:

void iterQuick(int a[], int l, int r) {
    int *stack = new int[(r-l)+1];
    int top = -1;
    stack[++top] = l;
    stack[++top] = r;
    while (top >= 0) {
        r = stack[top--];
        l = stack[top--];
        int i = partition(a, l, r);
        if (i - 1 > l) {
                stack[++top] = l;
                stack[++top] = i - 1;
        }
        if (i + 1 < r) {
                stack[++top] = i + 1;
                stack[++top] = r;
        }
    }
}

By using an array for our stack the work of setting up function calls to external push() and pop() methods is avoided, leading to a slightly faster run time. If however, you would still prefer the (arguably) cleaner interface of an ADT, the algorithm doesnt change:

void sort(int a[], int l, int r) {
    stack<int> sf;
    sf.push(l); sf.push(r);
    while (!sf.empty()) {
        r = sf.top(); sf.pop();
        l = sf.top(); sf.pop();
        if (r - l < 7) {
            insertionsort(a, l, r);
        } else {
            int i = partition(a, l, r);
            if (i-1 - l > 0) { sf.push(l); sf.push(i-1); }
            if (r - i+1 > 0) { sf.push(i+1); sf.push(r); }
        }
    }
}

Optimizations for Iterative Quicksort

With the recursion removed there are still a several optimizations we can use to squeeze a couple more horsepower from our algorithm.  One such optimization is pushing the smaller array to the stack first so that the larger of the two subarrays gets sorted before the smaller. We can also observe that in the above algorithm, we are pushing 2 pairs of values to the stack, and the immediately removing one one of them. We can fix this redundant push/pop with a method similar to tail call elimination in recursive algorithms, except instead of replacing a recursive call with a loop, we replace pushing one of the pairs to the stack. This optimization is covered in Sedgewick's "Algorithms in C++". In addition, it should be noted that most optimizations that work for the recursive implementation are directly transferable to the iterative version: Insertion sorting arrays below a certain threshold being one such optimization. Proper pivot selection also goes a very long way to avoiding worst case behavior in quicksort with randomized pivot selection, Median of three, or Median of Medians can all be dropped right in.

The following code is an example of iterative quicksort with median of 3 pivot selection, small array insertion sort, and sorting larger sub array first with tail call elimination.

const int CUTOFF = 6;

void insertionsort(int a[], int l, int r) {
    for (int i = l; i <= r; i++) {
        int j = i, v = a[i];
        while (j > l && a[j - 1] > v) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = v;
    }
}

void exch(int a[], int l, int r) {
    int tmp = a[l];
    a[l] = a[r];
    a[r] = tmp;
}

void medOf3(int a[], int l, int r) {
    cout<<"Median of 3."<<endl;
    int m = (l+r)/2;
    if (a[l] > a[m]) exch(a, l, m);
    if (a[l] > a[r]) exch(a, l, r);
    if (a[m] > a[r]) exch(a, m, r);
    exch(a, m, r);
}

void push(int stack[], int& top, int l, int r) {
    stack[++top] = l;
    stack[++top] = r;
}

void iterQuick(int a[], int l, int r) {
    int *stack = new int[(r-l)+1];
    int top = -1;
    while (true) {
        if (r - l < CUTOFF) {
            insertionsort(a, l, r);
        } else {
            while (r > l) {
                int i = partition(a, l, r);
                if ((i-1) - l < r - (i+1)) {
                    if (i - 1 > l) push(stack, top, l, i - 1);
                    l = i + 1;
                } else {
                    if (i + 1 < r) push(stack, top, i+1, r);
                    r = i - 1;
                }
            }
        }
        if (top < 0)
            break;
        r = stack[top--];
        l = stack[top--];
    }
}

Introsort, a hybrid of recursive Quicksort found in the C++ standard library as std::sort. Introsort works by switching to heapsort when the stack depth indicates that Quicksort is approaching its worst case. Interestingly, the optimization of pushing the smaller array onto the stack first when combined with tail call elimination gurantees the number of items on the stack will not exceed log N. As such, it would be interesting to see how much faster - if at all introsort actually is when compared to a properly tuned iterative quicksort, as introsort only switches to heapsort when the stack depth exceeds 2*logN.

 

---