The Quick Sort has long been considered the fastest sorting algorithm that a programmer can use. It's logic depends on the use of recursion, which stated simply means that the procedure calls itself causing a loop. It can sort either string or numeric data depending on your needs with very little modification. Here is the code for the QuickSort module I've written.

    Listing Of QuikSort.bas module

Public UpperBound As Long 
Public LowerBound As Long 
Public J As Long

Public Sub QuickSort(TheArray() As Person) 

    LowerBound = LBound(TheArray) 
    
UpperBound = UBound(TheArray) 
    Rearrange TheArray(), 
LowerBound, UpperBound 
    Quick TheArray(), LowerBound, 
UpperBound 
End Sub 
Public Sub Quick(TheArray() As Person, LowerBound 
As Long, UpperBound As Long) 
    If LowerBound < 
UpperBound Then 
        Rearrange 
TheArray(), LowerBound, UpperBound 

        Quick TheArray(), LowerBound, J - 
1 
        Quick TheArray(), J + 1, 
UpperBound 
    End If 
End Sub 
Public Sub Rearrange(TheArray() As Person, 
LowerBound As Long, UpperBound As Long) 
    Dim A As String 
    Dim Up As Long 

    Dim Down As Long 
    Dim Temp As Person 
    A = TheArray(LowerBound).BirthName 
    J 
= LowerBound 
    Up = UpperBound 
    Down 
= LowerBound 
    Do 

        DoEvents 

        While (Up 
> Down) And (TheArray(Up).BirthName >= A) 

            DoEvents 

            Up = Up - 
1 
        Wend 

        J = Up 

        If Up <> Down Then 

            Temp = 
TheArray(Up) 

            
TheArray(Up) = TheArray(Down) 

            
TheArray(Down) = Temp 

           While (Down < Up) And (TheArray(Down).BirthName < A) 

                
DoEvents 

                
Down = Down + 1 

            Wend 

        J = Down 

        If Down <> Up Then 

            Temp = 
TheArray(Up) 

            
TheArray(Up) = TheArray(Down) 

            
TheArray(Down) = Temp 

            End If 

        End If 
    
Loop Until (Down = Up) 
End Sub 

The Quick Sort algorithm is also a partitioning sort. This means that each pass through the Quick() routine it sorts "part of" the array, first the upper portion, then the lower portion. Each time the Quick() routine is called, it is passed pointers to the upper, and lower bounds of a portion of the array to be sorted.

On the originating call to the QuickSort() routine that starts the sort up, these will be set to the actual lower, and upper bounds of the array. Here is the originating call to the QuickSort() routine.

        QuickSort.QuickSort People()

The above call is made from a form in the project, so it requires pointing to the module which contains the sorting code. The code assumes People() to be a public array declared in a module. People is an array of type Person which is a UDT [user defined type] with at least the following structure.

Public Type Person
    BirthName As String
End Type

Public People() As Person

You can easily modify the code to work on an array of string, integer, or real data types, by changing the lines in red in the example routines to remove the reference to .BirthName, reflect the proper data types for the variables, and by changing the declaration of the array type passed in.

Note that when sorting string types the sort is case sensitive, so you may need to pre-process the array to insure case consistency of at least the first letter of the string values, unless you intend for the data to be case sensitively sorted.

Ok, now lets get down to figuring out how this thing works.

I know that this will be a bit hard to follow, but to help you out I've marked up a copy of the QuickSort() module with debug statements, which printed out a pretty good account of what's going on, if you refer to it alongside this explanation. I've edited it a bit to make it even clearer.

The result of that debug session is here: Debug of QuickSort()  Print it out, or open it in another tab, and refer to it while reading this page, this will make things a bit easier to follow.

First lets take a look at the QuickSort() subroutine again

Public Sub QuickSort(TheArray() As Person)
    LowerBound = LBound(TheArray)
    UpperBound = UBound(TheArray)
    Rearrange TheArray(), LowerBound, UpperBound
    Quick TheArray(), LowerBound, UpperBound
End Sub

As you can see here, the QuickSort() routine does an initial call to Rearrange(), after determining the upper, and lower bounds of the array passed in. This first call to Rearrange() receives the entire array as one partition.

Let's make up some data to sort, and give a look at how it works. To make it a bit easier to follow, I'm going to use an array of integer values instead of birth names. Here is an array of unsorted integers:

    5    3    2    9    7    8    UpperBound = 5 and LowerBound = 0

We fall first into Rearrange(), which first records the value of the lowest element of the current partition, in this case the bottom element in the array, and stores the passed in values for the partition to be sorted on this pass.

Note that all comments within the code examples are in the color Green.

    A = TheArray(LowerBound)     [A = 5]
    J = LowerBound
    Up = UpperBound
    Down = LowerBound
    Do 'outer loop start
        DoEvents
        While (Up > Down) And (TheArray(Up) >= A)
            DoEvents
            Up = Up - 1
        Wend
        J = Up

The first inner loop of Rearrange() starts comparing the values in the array to the value of A, starting at the last element in the array, and terminates when it encounters a value which is less than A. Here it will exit when it encounters the 2 in the third data element of the array.

It increments the value of Up on each pass through the loop, and upon exiting the new value of Up is recorded in the variable J. The value of J is now 2, since the array indexes start at zero.

    [A = 5] [Up = 2] [J = 2]

At this point the actual swapping of data elements occurs. We have to insure that we don't do an unnecessary swap of one element over itself, so we test to insure that Up <> Down before doing the swap.

        If Up <> Down Then
            Temp = TheArray(Up)
            TheArray(Up) = TheArray(Down)
            TheArray(Down) = Temp

Now the array looks like the following:

    2    3    5    9    7    8

We now proceed to the second inner loop, which searches from the bottom of the current partition upwards through the array, looking for an element which is less than 5. Note that this second inner loop is within the same If statement as the data element swap, so it doesn't run if Up = Down.

In this case it searches to the 5, at which point Up equals Down, so we fall out of the loop, and store Down's new value of 2 in J. The nested If then once again tests to see if Up <> Down, and if it isn't, it does an element swap again. Since Up = 2 and Down = 2 at this point no swap occurs.

            While (Down < Up) And (TheArray(Down) < A)
                DoEvents
                Down = Down + 1
            Wend
        J = Down
        If Down <> Up Then
            Temp = TheArray(Up)
            TheArray(Up) = TheArray(Down)
            TheArray(Down) = Temp
            End If
        End If

We've also hit the end of the outer loop at this point as now Up = Down. We now have the following values as we exit the first call to Rearrange().

    2    3    5    9    7    8    Down = 2    Up = 2    J = 2

Falling out of the outer loop we encounter the first call to Quick(), which is the recursive routine of the QuickSort(). Things now get a bit harder to follow, but not impossible. Here's the call to it again:

        Quick TheArray(), LowerBound, UpperBound

LowerBound and UpperBound have not changed, so we're still passing the entire array that has been pre-sorted a bit by the first call to Rearrange(). Looking at the Quick routine again we see:

Public Sub Quick(TheArray() As Person, LowerBound As Long, UpperBound As Long)
    If LowerBound < UpperBound Then
        Rearrange TheArray(), LowerBound, UpperBound
        Quick TheArray(), LowerBound, J - 1
        Quick TheArray(), J + 1, UpperBound
    End If
End Sub

The first thing we're going to do is call the Rearrange() sub again. Here we go with it's step through.

First we set A = 2, which is now the lowest element in the array. The first loop looks downward through the array, looking for a value smaller than 2. It doesn't find one, so we fall out, and record the new value of Down in J, which now equals 0.

Up equals Down, so no element swap occurs. The If statement containing the second inner loop fails, due to Up being equal to Down, and the outer loop test also is satisfied, so we've fallen right through the Rearrange() routine with the new value of J = 0 being the only change.

Now look closely at the recursive call to Quick() that follows the Rearrange() call. This time we're passing the value of negative one to Quick() as the upperbound of the partition to sort, so the first test in Quick() fails, and the first recursion ends.

When we fall out of it, we again recursively call Quick() with the unchanged value of J from the original Quick() routine called. We're now passing the partition from J + 1 to UpperBound to the Quick() routine.

    3    5    9    7    8

Quick() checks to insure that LowerBound is less than UpperBound. LowerBound has been passed in as 1, and UpperBound is still set to the upperbound of the original array.

Rearrange() sets A to 3, and once again quickly loops down through the partition finding no smaller values to swap it with. J gets set to 1, and we fall out of rearrange.

We're still inside of the second recursive call to Quick(), so we encounter yet another recursive call to Quick(), but this time we pass it the partition consisting of only the first element of the array. The LowerBound < UpperBound test fails, and we exit that recursion to the second instance called.

Now we call Quick() again, and pass Rearrange() the following partition:

    5    9    7    8    Down = 2    Up = 5    J = 2    A = 5

Up decrements to 2, where we find the value 5 in the array, and J gets set to 2. All subsequent tests fail, and we fall out of Rearrange() to the next recursive call to Quick().

Lowerbound at this point is passed in as 2, and UpperBound as 1, so this recursion ends quite quickly due to LowerBound being greater than UpperBound.

Since J is still equal to 2, we pass the partition from element 3 to element 5 to the next call to Quick(), where J + 1 is passed in. This time the data looks like so:

    9    7    8    A = 9    J = 3    Down = 3    Up = 5

Rearrange immediately finds an 8 in the last array position, and swaps it with the 9 in position 3. Now we have the partition:

    8    7    9    A = 9    J = 5    Up = 5

The second inner loop increments Down to 5 finding no values greater than 9. J gets set to 5 which it already was, and we fall out of Rearrange() again.

The next recursion is passed LowerBound of 3, and UpperBound of 4. This partition consists of the two elements, and values shown below:

    8    7    A = 8    J = 3    Down = 3    Up = 4

The first inner loop finds the 7, and J gets set to 4. The values 8 and 7 get swapped and we have:

    7    8    A = 8    J  = 4    Down = 3    Up = 4

The second inner loop increments to 4, and J gets set to 4, the rest of the tests fail, and we fall out of Rearrange().

At this point the array has been completely sorted.

The next recursion gets passed equal values for UpperBound, and LowerBound, so it exits quickly, and the next recursion gets passed a larger value for LowerBound than UpperBound so it also exits.

We've reached the end of the outer recursive call now, so we exit it to the previously called instance, which has one call to Quick() left. It calls it with the values of 5 for both LowerBound, and UpperBound, and quickly exits.

We're now past the recursive calls in all of the previously called instances of Quick() at this point, so we fall out of all of them in turn, and the recursive looping ends.

I hope this has helped you understand how the QuickSort routine works.