What's New
Q & A
Tip Jar
C# Helper...
Follow VBHelper on Twitter
MSDN Visual Basic Community
TitleSort a list using quicksort in VB .NET
DescriptionThis example shows how to sort a list using quicksort in VB .NET.
Keywordssorting, quicksort, algorithms
The quicksort subroutine takes as parameters a list to sort and the minimum and maximum index of the elements it should sort. It randomly selects a value within the items to sort and uses it as a dividing item. It then moves all of the items that are smaller than this item to the front of the list and all of those larger than the dividing item to the end of the list. It then recursively calls itself to sort the two sublists.
Public Sub Quicksort(ByVal list() As Integer, ByVal min As _
    Integer, ByVal max As Integer)
    Dim random_number As New Random
    Dim med_value As Integer
    Dim hi As Integer
    Dim lo As Integer
    Dim i As Integer

    ' If min >= max, the list contains 0 or 1 items so
    ' it is sorted.
    If min >= max Then Exit Sub

    ' Pick the dividing value.
    i = random_number.Next(min, max + 1)
    med_value = list(i)

    ' Swap it to the front.
    list(i) = list(min)

    lo = min
    hi = max
        ' Look down from hi for a value < med_value.
        Do While list(hi) >= med_value
            hi = hi - 1
            If hi <= lo Then Exit Do
        If hi <= lo Then
            list(lo) = med_value
            Exit Do
        End If

        ' Swap the lo and hi values.
        list(lo) = list(hi)

        ' Look up from lo for a value >= med_value.
        lo = lo + 1
        Do While list(lo) < med_value
            lo = lo + 1
            If lo >= hi Then Exit Do
        If lo >= hi Then
            lo = hi
            list(hi) = med_value
            Exit Do
        End If

        ' Swap the lo and hi values.
        list(hi) = list(lo)

    ' Sort the two sublists.
    Quicksort(list, min, lo - 1)
    Quicksort(list, lo + 1, max)
End Sub
See my book Ready-to-Run Visual Basic Algorithms for more information on this and other sorting algorithms. Note that quicksort works very well with lists that are initially randomly arranged and that do not contain too many duplicate values. Under other circumstances, see the book for better sorting algorithms.
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.