Access Cookbook - Ken Getz [156]
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.
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