DOCUMENT:Q169617 29-APR-2001 [vbwin]
TITLE :HOWTO: Sort Algorithms for Numeric Arrays
PRODUCT :Microsoft Visual Basic for Windows
PROD/VER::4.0,5.0,6.0
OPER/SYS:
KEYWORDS:kbsample KbVBA kbVBp kbVBp400 kbVBp500 kbVBp600 kbGrpDSVB kbDSupport
======================================================================
-------------------------------------------------------------------------------
The information in this article applies to:
- Microsoft Visual Basic Enterprise Edition for Windows, versions 4.0, 5.0, 6.0
- Microsoft Visual Basic Professional Edition for Windows, versions 4.0, 5.0, 6.0
- Microsoft Visual Basic for Applications versions 5.0, 6.0
-------------------------------------------------------------------------------
SUMMARY
=======
This article demonstrates how to use sort algorithms for sorting numeric arrays.
It describes three methods of sorting a series of numbers and provides sample
code that shows how to implement them with the time taken to sort by each
algorithm.
MORE INFORMATION
================
It is often necessary to sort a series of numbers in code, and there are various
sorting algorithms available to do this.
This article includes three methods:
- Bubble sort
- Selection sort
- Shell sort
Each routine simply receives an array full of numbers within the bounds of a LONG
datatype, although this could be easily changed for different numeric datatypes.
Note that the sort routines return the result of the sort operation in the array
that is passed to the routine. Therefore, if you do not want the original array
to be modified, copy the array to a variant, as shown in the example below, and
then pass the variant to the relevant procedure.
Step-by-Step Example
--------------------
1. Start a new Standard EXE project in Visual Basic. Form1 is created by
default.
2. Place a CommandButton (Command1) onto Form1.
3. Add the following code in the code window of Form1:
Option Explicit
Dim startTime As Double
Dim endTime As Double
Dim timeToSort As Double
Dim timeTaken As String
Sub Command1_Click()
Dim lMyArray(0 To 2000) As Long
Dim vTemp1 As Variant
Dim vTemp2 As Variant
Dim vTemp3 As Variant
Dim iLoop As Integer
Randomize
For iLoop = LBound(lMyArray) To UBound(lMyArray)
lMyArray(iLoop) = Int(Rnd * 100) + 1
Next iLoop
vTemp1 = lMyArray
vTemp2 = lMyArray
vTemp3 = lMyArray
Screen.MousePointer = vbHourglass
Call BubbleSortNumbers(vTemp1)
Call SelectionSortNumbers(vTemp2)
Call ShellSortNumbers(vTemp3)
Screen.MousePointer = vbDefault
MsgBox timeTaken
End Sub
Sub BubbleSortNumbers(iArray As Variant)
Dim lLoop1 As Long
Dim lLoop2 As Long
Dim lTemp As Long
startTime = Time()
For lLoop1 = UBound(iArray) To LBound(iArray) Step -1
For lLoop2 = LBound(iArray) + 1 To lLoop1
If iArray(lLoop2 - 1) > iArray(lLoop2) Then
lTemp = iArray(lLoop2 - 1)
iArray(lLoop2 - 1) = iArray(lLoop2)
iArray(lLoop2) = lTemp
End If
Next lLoop2
Next lLoop1
endTime = Time()
timeToSort = endTime - startTime
timeTaken = "Bubble Sort: " & timeToSort
End Sub
Sub SelectionSortNumbers(vArray As Variant)
Dim lLoop1 As Long
Dim lLoop2 As Long
Dim lMin As Long
Dim lTemp As Long
startTime = Time()
For lLoop1 = LBound(vArray) To UBound(vArray) - 1
lMin = lLoop1
For lLoop2 = lLoop1 + 1 To UBound(vArray)
If vArray(lLoop2) < vArray(lMin) Then lMin = lLoop2
Next lLoop2
lTemp = vArray(lMin)
vArray(lMin) = vArray(lLoop1)
vArray(lLoop1) = lTemp
Next lLoop1
endTime = Time()
timeToSort = endTime - startTime
timeTaken = timeTaken & "; Selection Sort: " & timeToSort
End Sub
Sub ShellSortNumbers(vArray As Variant)
Dim lLoop1 As Long
Dim lHold As Long
Dim lHValue As Long
Dim lTemp As Long
startTime = Time()
lHValue = LBound(vArray)
Do
lHValue = 3 * lHValue + 1
Loop Until lHValue > UBound(vArray)
Do
lHValue = lHValue / 3
For lLoop1 = lHValue + LBound(vArray) To UBound(vArray)
lTemp = vArray(lLoop1)
lHold = lLoop1
Do While vArray(lHold - lHValue) > lTemp
vArray(lHold) = vArray(lHold - lHValue)
lHold = lHold - lHValue
If lHold < lHValue Then Exit Do
Loop
vArray(lHold) = lTemp
Next lLoop1
Loop Until lHValue = LBound(vArray)
endTime = Time()
timeToSort = endTime - startTime
timeTaken = timeTaken & "; Shell Sort: " & timeToSort
End Sub
4. Run the project, and click Command1. You receive the following output or
similar:
Bubble Sort: 4.6296E -05; Selection Sort: 3.4722E -05; Shell Sort: 0
NOTE: In most cases, the Shell sort is the fastest of the three sorts presented.
To determine which sort is faster, you can also use the QueryPerformanceCounter
function to time the application code.
REFERENCES
==========
For additional information on how to use the QueryPerformanceCounter function,
click the article number below to view the article in the Microsoft Knowledge
Base:
Q172338 HOWTO: Use QueryPerformanceCounter to Time Code
Additional query words:
======================================================================
Keywords : kbsample KbVBA kbVBp kbVBp400 kbVBp500 kbVBp600 kbGrpDSVB kbDSupport
Technology : kbVBSearch kbAudDeveloper kbZNotKeyword6 kbZNotKeyword2 kbVB500Search kbVB600Search kbVBA600Search kbVBA500 kbVBA600 kbVB500 kbVB600 kbVB400Search kbVB400 kbVBASearch kbZNotKeyword3
Version : :4.0,5.0,6.0
Issue type : kbhowto
=============================================================================
THE INFORMATION PROVIDED IN THE MICROSOFT KNOWLEDGE BASE IS
PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. MICROSOFT DISCLAIMS
ALL WARRANTIES, EITHER EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO
EVENT SHALL MICROSOFT CORPORATION OR ITS SUPPLIERS BE LIABLE FOR
ANY DAMAGES WHATSOEVER INCLUDING DIRECT, INDIRECT, INCIDENTAL,
CONSEQUENTIAL, LOSS OF BUSINESS PROFITS OR SPECIAL DAMAGES, EVEN IF
MICROSOFT CORPORATION OR ITS SUPPLIERS HAVE BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES. SOME STATES DO NOT ALLOW THE EXCLUSION
OR LIMITATION OF LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES
SO THE FOREGOING LIMITATION MAY NOT APPLY.
Copyright Microsoft Corporation 2001.