# Quicksort (Visual Basic .NET)

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

## 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", _
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
```