Quicksort (Visual Basic .NET)

From LiteratePrograms

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

Contents 1 Overview 2 The algorithm 3 Pivot 4 Partition 5 Test

Overview

Quick sort works like this:

• Select a pivot value in the data to be sorted
• Move all smaller elements to the beginning of the array
• Repeat recursively for both smaller and bigger values

This implementation works on an array of Objects.

The algorithm

The quicksort sub-routine takes 3 arguments.

• a - The array to be sorted
• left - Index of the first element in the range to be sorted
• right - Index of the first element not in the range to be sorted

After checking if the sort range is empty or contain only 1 element, we use the getpivot function to get the index of a pivot value. The partition function arranges the values so that all elements smaller than the pivot value are on the left side of the pivot. The returned value is the new index of the pivot value.

The final step is to recursively call quicksort on the left and right sides of the pivot.

<<quicksort>>=
    Sub quicksort(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
        Dim pivot As Integer
        If right - left > 1 Then
            pivot = getpivot(a, left, right)
            pivot = partition(a, left, right, pivot)
            quicksort(a, left, pivot)
            quicksort(a, pivot + 1, right)
        End If
    End Sub

Since most users are interested in sorting the complete array, we provide the qsort sub routine as a simplified interface to quicksort.

To avoid bad performance when the input is sorted or nearly sorted, we randomise the array before sorting.

<<qsort>>=
    Sub qsort(ByRef a() As Object)
        Dim i
        Dim ii
        For i=0 to a.Length()-1
            ii=New System.Random().Next(0, a.Length()-1)
            If i<>ii Then
                swap(a(i), a(ii))
            End If
        Next
        quicksort(a, 0, a.Length())
    End Sub

Pivot

The getpivot function will return the index of a random element in the range to be sorted. Another popular pivot choise is using median of first, middle and last element.

<<getpivot>>=
    Function getpivot(ByRef a() As Object, ByVal left As Integer, ByVal right As Integer)
        return New System.Random().Next(left, right - 1)
    End Function

Partition

<<partition>>=
    Function partition(ByRef a() As Object, ByVal left As Integer, _
    ByVal right As Integer, ByRef pivot As Integer)
        Dim i
        Dim piv
        Dim store
        piv = a(pivot)
        swap(a(right - 1), a(pivot))
        store = left
        For i = left To right - 2
            If a(i) <= piv Then
                swap(a(store), a(i))
                store = store + 1
            End If
        Next
        swap(a(right - 1), a(store))
        Return store
    End Function

<<swap>>=
    Sub swap(ByRef v1, ByRef v2)
        Dim tmp
        tmp = v1
        v1 = v2
        v2 = tmp
    End Sub

Test

This test program will first run qsort on an array of string objects, and then do the same on an array of Integer objects.

<<quicksort.vb>>=
Module Quicksort
swap
partition
getpivot
quicksort
qsort
    Sub print(ByRef a() As Object)
        Dim i
        For i = 0 To a.Length() - 1
            System.Console.Write("  " & a(i))
        Next
        System.Console.WriteLine()
    End Sub
    Sub main()
        Dim towns() As Object = {"Paris", "London", "Stockholm", "Berlin", "Oslo", "Rome", _
        "Madrid", "Tallinn", "Amsterdam", "Dublin"}
        System.Console.Write("towns before qsort: ")
        print(towns)
        qsort(towns)
        System.Console.Write("towns after qsort: ")
        print(towns)
        Dim numbers() As Object = {5, 7, 5, 2, 8, 4, 6, 2, 3, 5, 1, 8, 5, 7, 3}
        System.Console.Write("numbers before qsort: ")
        print(numbers)
        qsort(numbers)
        System.Console.Write("numbers after qsort: ")
        print(numbers)
    End Sub
End Module

Download code