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.