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.
7.7.4 See Also
See the next solution for an example of using
QuickSort .