


Visual Basic
Sort Routine Library Pure VB: Applying and Understanding the QuickSort 

Posted:  Saturday April 1, 2000  
Updated:  Monday December 26, 2011  
Applies to:  VB3, VB416, VB432, VB5, VB6  
Developed with:  VB6, Windows NT4  
OS restrictions:  None  
Author:  VBnet  Randy Birch  
Related: 
Pure VB: Quick, Shell, Bubble and Selection Sort Performance Comparisons


Prerequisites 
None. 

Probably the most useful sort for VB programmers against
singledimensioned arrays is the QuickSort method.
The QuickSort routine also provides pretty well the fastest sort amongst the common sort methods  BubleSort, ShellSort, MergeSort, InsertionSort and QuickSort. Its operation is fairly straightforward: an item is chosen midway between two points in array() (called the pivot point). One value that is higher and one value that is lower than the pivot point is found and swapped, with the function calling itself passing new start and stop points. The method continues in this fashion until no elements meet these conditions, at which point the array is sorted. Within VB, I've found the QuickSort has to be the easiest sort routine to implement just about anywhere that a fast and efficient sorting algorithm is required. It's easily customized for different data types (integer, long, double, variant etc.), and can be coded to sort in ascending or descending order by flipping the comparisons (i.e. "If x < y" to "If x > y"). And if that's not enough, with a bit more work its capabilities can be applied against the data in a grid, or even a userdefined type (UDT). Presented below is the basic QuickSort routine for Variants, uncommented and ready to use, followed by a complete description of the logic. Note: On this page only, the "copy bas code" button (for IE users only) copies the brief, uncommented code. The "copy form code" button copies the fullycommented code. Otherwise, both sets of code are identical and only one of these two options is required for your app. 
The Basic QuickSort Method 
This can be in either a form or bas module, as needed. The variables passed to the procedure should be typed correctly (i.e. Long, Integer, String etc.) to maximize performance. 

Option Explicit '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ' Copyright ©19962011 VBnet/Randy Birch, All Rights Reserved. ' Some pages may also contain other copyrights by the author. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ' Distribution: You can freely use this code in your own ' applications, but you may not reproduce ' or publish this code on any web site, ' online service, or distribute as source ' on any media without express permission. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' Public Sub QuickSortVariants(vArray As Variant, inLow As Long, inHi As Long) Dim pivot As Variant Dim tmpSwap As Variant Dim tmpLow As Long Dim tmpHi As Long tmpLow = inLow tmpHi = inHi pivot = vArray((inLow + inHi) \ 2) While (tmpLow <= tmpHi) While (vArray(tmpLow) < pivot And tmpLow < inHi) tmpLow = tmpLow + 1 Wend While (pivot < vArray(tmpHi) And tmpHi > inLow) tmpHi = tmpHi  1 Wend If (tmpLow <= tmpHi) Then tmpSwap = vArray(tmpLow) vArray(tmpLow) = vArray(tmpHi) vArray(tmpHi) = tmpSwap tmpLow = tmpLow + 1 tmpHi = tmpHi  1 End If Wend If (inLow < tmpHi) Then QuickSortVariants vArray, inLow, tmpHi If (tmpLow < inHi) Then QuickSortVariants vArray, tmpLow, inHi End Sub 
How the QuickSort Works 
This is the same code as above, fully commented. The magic behind the sort ... 

Option Explicit Public Sub QuickSortVariants(vArray As Variant, inLow As Long, inHi As Long) 'vArray() The array to sort 'inLow Lower bound of sort point 'inHi Upper bound of sort point 'Dim two working variables to hold 'array members. The first holds the 'pivot item  the item half way between 'the inLow and inHi values, while the 'second is used to hold the array contents 'that will be swapped later. 'These two items should be declared as 'the same data type as the array passed. Dim pivot As Variant Dim tmpSwap As Variant 'Dim two working variables to hold the 'values representing the pivot's lower 'and upper points as passed to the routine. 'These should be declared as the same data 'type as the inLow/inHi variables passed. Dim tmpLow As Long Dim tmpHi As Long 'Save to the working variables the 'values passed as lower & upper tmpLow = inLow tmpHi = inHi 'Get the item halfway through the data 'determined by the range passed as lower 'and upper and assign it as the pivot data ' 'When first calling this routine the 'range is inLow = LBound(array), and 'inHi = UBound(array). During subsequent 'calls, inLow and inHi will receive 'different values as determined below. pivot = vArray((inLow + inHi) \ 2) 'With pivot holding the value of the item 'halfway through the range, compare the 'rank of tmpLow to tmpHi and assign the two 'tmp storage variables that data for later 'comparison. Here we're continuing the loop 'while the low item being compared value (tmpLow) 'is less than tmpHi (the upper bound value). While (tmpLow <= tmpHi) 'Since (and while) tmpLow remains less than 'tmpHi, compare the value of the array() 'element at this position against pivot. While (vArray(tmpLow) < pivot And tmpLow < inHi) tmpLow = tmpLow + 1 Wend 'repeat the same for the array value at 'position tmpHi. While (pivot < vArray(tmpHi) And tmpHi > inLow) tmpHi = tmpHi  1 Wend 'When the position of tmpHi exceeds or matches tmpLow 'swap the two items. If (tmpLow <= tmpHi) Then 'a: assign vArray(tmpLow) to tmpSwap 'b: swap vArray(tmpHi) for vArray(tmpLow) 'c: assign tmpSwap back to vArray(tmpHi) tmpSwap = vArray(tmpLow) vArray(tmpLow) = vArray(tmpHi) vArray(tmpHi) = tmpSwap 'adjust the new Hi and Low values tmpLow = tmpLow + 1 tmpHi = tmpHi  1 End If Wend 'if the original lower is less than tmpHi, 'call the routine again with inLow & tmpHi 'as the pivot's lower and upper points. If (inLow < tmpHi) Then QuickSortVariants vArray, inLow, tmpHi 'if the new tmpLow value lower is less than 'the original inHi, call the routine again with 'tmpLow & inHi as the pivot's lower and upper points. If (tmpLow < inHi) Then QuickSortVariants vArray, tmpLow, inHi End Sub 
Comments 








Copyright ©19962011 VBnet and Randy Birch. All Rights Reserved. 