[VBnet Sort] Pure VB: Applying and Understanding the QuickSort


	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, VB4-16, VB4-32, 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 Pure VB: QuickSort Variations Pure VB: Sorting Date Arrays using QuickSort Pure VB: Applying and Understanding the QuickSort

Prerequisites

None.

Probably the most useful sort for VB programmers against single-dimensioned 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 user-defined 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 fully-commented 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 ©1996-2011 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

PayPal Link