Home Search   What's New Index Books Links Q & A Newsletter Banners   Feedback Tip Jar MSDN Visual Basic Community

Title Sort a list using quicksort in VB .NET This example shows how to sort a list using quicksort in VB .NET. sorting, quicksort, algorithms 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
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```

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.