Recipe 7.7 Sort an Array in VBA

7.7.1 Problem

Although it's a database product, Access doesn't include a way to sort an array. You need to present sorted arrays in an application, and you can't find a reasonable way to sort them without first saving them to a table. You know you've seen array-sorting methods in other languages. Can you write a sorting routine that executes quickly?

7.7.2 Solution

It's true that Access doesn't provide a built-in sorting mechanism for arrays. Entire volumes in libraries are devoted to the study of various sorting and searching algorithms, but it's not necessary to dig too deep for array-sorting methods for Access. Because you'll probably place any large data sets into a table, most arrays in Access aren't very large. Therefore, almost any sort will do. This solution uses a variant of the standard quicksort algorithm. (For more information on various sorting and searching algorithms, consult your computer library. This is a big topic!)

To try the sorting mechanism, load the module named basSortDemo in 07-07.MDB. From the Immediate window, type:

TestSort 6

where the 6 can be any integer between 1 and 20, indicating the number of random integers between 1 and 99 that you want the routine to sort. The sample routine, TestSort, will create the array of integers and send it off to VisSortArray, a special version of the sorting routine acbSortArray that shows what it's doing as it works. Figure 7-11 shows the output from a sample session.

Figure 7-11. The output from a sample run of TestSort

To use this sorting code in your own applications, follow these steps:

Import the module named basSortArray into your application.
Create the array you'd like to sort. This must be an array of variants, but those variants can hold any datatype; this solution uses an array of Integers and the Solution in Recipe 7.8 uses an array of Strings.
Call acbSortArray, passing to it the name of the array you'd like to sort. For example, to sort an array named avarStates, use the following call:
```
acbSortArray avarStates( )
```
After the call to acbSortArray, your array will be sorted. Remember that acbSortArray is sorting your array in place: once it's sorted, there's no going back! If you don't want to sort your only copy of the array, make a duplicate first.

7.7.3 Discussion

The quicksort algorithm works by breaking the array into smaller and smaller chunks, sorting each one, until all the chunks are one element long. The acbSortArray procedure calls the main sorting routine, QuickSort, passing to it the array and the start and end points for sorting. The QuickSort routine breaks the array into two chunks, then calls itself twice to sort each of the two halves.

At this point, you might be grumbling about recursive routines and how they use lots of memory. Normally, that's true. This version of the sorting algorithm, however, tries to be conservative about how it uses memory. At each level, it sorts the smaller of the two chunks first. This means that it will have fewer recursive levels: the small chunk will end up containing a single element much more quickly than the large chunk. By always working with the smallest chunk first, this method avoids calling itself more often than it has to.

The code for the QuickSort procedure is:

Private Sub QuickSort(varArray As Variant, _
 intLeft As Integer, intRight As Integer)
    Dim i As Integer
    Dim j As Integer
    Dim varTestVal As Variant
    Dim intMid As Integer

    If intLeft < intRight Then
        intMid = (intLeft + intRight) \ 2
        varTestVal = varArray(intMid)
        i = intLeft
        j = intRight
        Do
            Do While varArray(i) < varTestVal
                i = i + 1
            Loop
            Do While varArray(j) > varTestVal
                j = j - 1
            Loop
            If i <= j Then
                SwapElements varArray( ), i, j
                i = i + 1
                j = j - 1
            End If
        Loop Until i > j
        ' To optimize the sort, always sort the
        ' smallest segment first.
        If j <= intMid Then
            QuickSort varArray( ), intLeft, j
            QuickSort varArray( ), i, intRight
        Else
            QuickSort varArray( ), i, intRight
            QuickSort varArray( ), intLeft, j
        End If
    End If
End Sub

The following are the basic steps of the QuickSort procedure. These steps use intLeft to refer to the beginning sort item and intRight for the ending item:

If intLeft isn't less than intRight, the sort is done.
The sort takes the value in the middle of the subset of the array that's being sorted as the "comparison" value. Its value will be the dividing factor for the two chunks. There are different schools of thought on how to choose the dividing item. This version of the sort uses the item that's physically in the middle of the chosen list of items:
```
intMid = (intLeft + intRight) \ 2
varTestVal = varArray(intMid)
```
The sort starts from the left, walking along the array until it finds an item that isn't less than the dividing value. This search is guaranteed to stop at the dividing value, which certainly isn't less than itself:
```
Do While varArray(i) < varTestVal
   i = i + 1
Loop
```
The sort starts from the right, walking backward through the array until it finds an item that isn't greater than the dividing value. This search is guaranteed to stop at the dividing value, which certainly isn't more than itself:
```
Do While varArray(j) > varTestVal
   j = j - 1
Loop
```
If the position from Step 3 is less than or equal to the position found in Step 4, the sort swaps the elements at the two positions, then increments the pointer for Step 3 and decrements the pointer for Step 4:
```
If i <= j Then
   SwapElements varArray( ), i, j
   i = i + 1
   j = j - 1
End If
```
The sort repeats Steps 3 through 5 until the pointer from Step 3 is greater than the pointer from Step 4 (i > j). At this point, every item to the left of the dividing element is less than or equal to it, and everything to the right is greater than or equal to it.

Choosing the smaller partition first, the sort repeats all these steps on each of the subsets to either side of the dividing value, until Step 1 indicates that it's done:

If j <= intMid Then
   QuickSort varArray( ), intLeft, j
   QuickSort varArray( ), i, intRight
Else
   QuickSort varArray( ), i, intRight
   QuickSort varArray( ), intLeft, j
End If

There are probably sort algorithms that are simpler than the quicksort algorithm, but for arrays that aren't already sorted, quicksort's speed is hard to beat. (For presorted arrays, it doesn't do as well as some other sorts. But most arrays don't come to the QuickSort subroutine in order.) As it is, the QuickSort subroutine is capable of handling only single-column arrays. If you need to sort multicolumn arrays, you'll need to either modify the code to handle those cases or move the data into a table and let Access do the sorting for you.