Iterative QuickSort

For every recursive algorithm, there is an iterative algorithm. In the first edition of this book, I challenged readers to write the iterative version of SortArray. Scott D. Killen answered the call with an implementation that used my CStack class to save sections of the array for later sorting. Scott credits the book Practical Algorithms in C++ (John Wiley and Sons, Inc., 1995) by Bryan Flamig as his source. Here’s the code:

‘ Iterative QuickSort algorithm
Sub SortArray(aTarget() As Variant, Optional vFirst As Variant, _
              Optional vLast As Variant, Optional helper As ISortHelper)
    Dim iFirst As Long, iLast As Long
    If IsMissing(vFirst) Then iFirst = LBound(aTarget) Else iFirst = vFirst
    If IsMissing(vLast) Then iLast = UBound(aTarget) Else iLast = vLast
    If helper Is Nothing Then Set helper = New CSortHelper
    
With helper
    Dim iLo As Long, iHi As Long, iRand As Long, stack As New CStack
    Do
        Do
            ‘ Swap from ends until first and last meet in the middle
            If iFirst < iLast Then
                ‘ If we’re in the middle and out of order, swap
                If iLast - iFirst = 1 Then
                    If .Compare(aTarget(iFirst), aTarget(iLast)) > 0 Then
                        .Swap aTarget(iFirst), aTarget(iLast)
                    End If
                Else
                    ‘ Split at some random point
                    .Swap aTarget(iLast), _
                          aTarget(MRandom.Random(iFirst, iLast))
                    ‘ Swap high values below the split for low values above
                    iLo = iFirst: iHi = iLast
                    Do
                        ‘ Find any low value larger than split
                        Do While (iLo < iHi) And _
                                 (.Compare(aTarget(iLo), aTarget(iLast)) <= 0)
                            iLo = iLo + 1
                        Loop
                        ‘ Find any high value smaller than split
                        Do While (iHi > iLo) And _
                                 (.Compare(aTarget(iHi), aTarget(iLast)) >= 0)
                            iHi = iHi - 1
                        Loop
                        ‘ Swap too high low value for too low high value
                        If iLo < iHi Then .Swap aTarget(iLo), aTarget(iHi)
                    Loop While iLo < iHi
                    ‘ Current (iLo) is larger than split (iLast), so swap
                    .Swap aTarget(iLo), aTarget(iLast)
                    ‘ Push range markers of larger part for later sorting
                    If (iLo - iFirst) < (iLast - iLo) Then
                        stack.Push iLo + 1
                        stack.Push iLast
                        iLast = iLo - 1
                    Else
                        stack.Push iFirst
                        stack.Push iLo - 1
                        iFirst = iLo + 1
                    End If
                    ‘ Exit from inner loop to process smaller part
                    Exit Do
                End If
            End If
            
            ‘ If stack empty, Exit outer loop
            If stack.Count = 0 Then Exit Sub
            ‘ Else pop first and last from last deferred section
            iLast = stack.Pop
            iFirst = stack.Pop
        Loop
    Loop
End With
End Sub

Scott’s code proves two points. First, iterative algorithms aren’t necessarily faster than recursive ones. If you check the two versions in the TimeIt application, you’ll see that the recursive version wins by half a hair. But in a race that close you have to give the advantage to the code that uses the least resources. The iterative version gets the nod as the official SortArray procedure in the VBCore component because it can never run out of stack space.

The second point is that recursive algorithms can be a lot simpler than iterative ones. In fact, I think of the recursive version as documentation for the iterative version. You can read the recursive code and it makes sense. Not so the iterative code. I stepped through it and added comments that attempt to explain what’s going on, but I still don’t really understand the details. Mainly I just pray that it works.

Don’t read too much into this particular result. You’ll have to analyze your algorithms on a case-by-case basis. Think carefully before you start trying to reorganize natural recursive algorithms into twisted iterative ones. For algorithms that don’t recurse deeply, saving stack space probably won’t matter. In fact,
32-bit programs aren’t nearly as likely to run out of stack space as were 16-bit programs. Sometimes iterative algorithms are clearer anyway. The iterative binary search algorithm at the end of this chapter could have been written recursively, but it wouldn’t have been any clearer.

The SortArray sub is used to sort arrays containing strings and integers in the Test Sort program (TSORT.VBP), shown in Figure 5-3. This program sorts arrays and is used in the implementation of sorted collections and a sorted list box control. For now, we’re interested only in arrays. (I’ve already discussed sorted collections and list boxes.) SortArray is also used to sort an array of playing cards in the Fun ’n Games program (FUNNGAME.VBP) described in Chapter 6.

Figure 5-3. The Test Sort program.

I’m embarrassed to admit that the recursive version of this algorithm in the first edition contained an example of one of the oldest and most pervasive bugs you can write. It made several assignments inside a loop that could just as easily have been made outside the loop. As a result, the function was four to five times slower than necessary. Sharp-eyed reader David Wilmer identified the problem. To make matters worse, the same bug actually showed up in five different places on the CD. I reported the problem and provided a fix (with abject apologies) on the Internet site for the book, but some readers might have missed it. My only excuse (a weak one) is that it wasn’t originally my bug. The code came from an old version of SORTDEMO, but I learned later that the bug and the fix were described years ago in the Knowledge Base for QuickBasic. I don’t spend a lot of time wandering through bug reports in defunct products, so I missed it. Sorry about that.