example shows how to sort a list using quicksort

[nandagopal]

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.

Code Select Expand


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
    Do
        ' Look down from hi for a value < med_value.
        Do While list(hi) >= med_value
            hi = hi - 1
            If hi <= lo Then Exit Do
        Loop
        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
        Loop
        If lo >= hi Then
            lo = hi
            list(hi) = med_value
            Exit Do
        End If

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

    ' Sort the two sublists.
    Quicksort(list, min, lo - 1)
    Quicksort(list, lo + 1, max)
End Sub