It’s unlikely that you will be asked to write code to do a quick sort from scratch in an A Level exam. Rather, you should understand and be able to explain the quicksort algorithm, and recognise the implementation code when you see it.
Below are 3 different VB.NET implementations of a function that will partition an unordered list. Notice that in each version, the function takes 3 parameters: the list to be sorted, a left pointer and a right pointer. When called, the function is passed the lower and upper bounds of the array as the left and right pointers. Any one of these versions could be used in a quicksort.
The final section of code is an example of a recursive quicksort procedure that makes use of one of the partitioning functions.
You could copy and paste these examples into a new VB.NET solution and experiment with them.
Partition a list – version 1
This version of a function to partition a list closely follows the algorithm which nominates the left most value of the list as a pivot.
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim aiData(7) As Integer
aiData(0) = 5
aiData(1) = 2
aiData(2) = 7
aiData(3) = 6
aiData(4) = 9
aiData(5) = 1
aiData(6) = 4
aiData(7) = 8
Dim stOut As String
stOut = "Original List" & vbNewLine & vbNewLine
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
stOut = stOut & vbNewLine & vbNewLine & "Partitioned List" & vbNewLine & vbNewLine
Call Partition(aiData, 0, 7)
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
MsgBox(stOut)
End Sub
Function Partition(ByRef aiData As Integer(), iLeft As Integer, iRight As Integer)
Dim iPivot As Integer
iPivot = aiData(iLeft)
Dim stCurrentPointer As String
stCurrentPointer = "Right"
Do While iLeft <> iRight
If stCurrentPointer = "Right" Then
If aiData(iRight) < iPivot Then
aiData(iLeft) = aiData(iRight)
iLeft = iLeft + 1
stCurrentPointer = "Left"
Else
iRight = iRight - 1
End If
ElseIf stCurrentPointer = "Left" Then
If aiData(iLeft) > iPivot Then
aiData(iRight) = aiData(iLeft)
iRight = iRight - 1
stCurrentPointer = "Right"
Else
iLeft = iLeft + 1
End If
End If
Loop
aiData(iLeft) = iPivot
Return iLeft
End Function
End Class
Partition a list – version 2
This is a modified version of a function to partition a list which also nominates the left most value of the list as a pivot.
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim aiData(7) As Integer
aiData(0) = 5
aiData(1) = 2
aiData(2) = 7
aiData(3) = 6
aiData(4) = 9
aiData(5) = 1
aiData(6) = 4
aiData(7) = 8
Dim stOut As String
stOut = "Original List" & vbNewLine & vbNewLine
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
stOut = stOut & vbNewLine & vbNewLine & "Partitioned List" & vbNewLine & vbNewLine
Call Partition2(aiData, 0, 7)
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
MsgBox(stOut)
End Sub
Function Partition2(ByRef aiData As Integer(), iLeft As Integer, iRight As Integer)
Dim iPivot As Integer
iPivot = aiData(iLeft)
Do While iLeft <> iRight
Do While (aiData(iRight) > iPivot) And (iLeft <> iRight)
iRight = iRight - 1
Loop
aiData(iLeft) = aiData(iRight)
Do While (aiData(iLeft) < iPivot) And (iLeft <> iRight)
iLeft = iLeft + 1
Loop
aiData(iRight) = aiData(iLeft)
Loop
aiData(iLeft) = iPivot
Return iLeft
End Function
End Class
Partition a list – version 3
This version of a function to partition a list does not explicitly nominate a pivot. Values at the left and right pointers are compared, each time the smaller value is moved to the left pointer, or the larger value is moved to the right pointer. In this version, the value that started at the right hand side of the list finds itself in the correct position.
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim aiData(7) As Integer
aiData(0) = 5
aiData(1) = 2
aiData(2) = 7
aiData(3) = 6
aiData(4) = 9
aiData(5) = 1
aiData(6) = 4
aiData(7) = 8
Dim stOut As String
stOut = "Original List" & vbNewLine & vbNewLine
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
stOut = stOut & vbNewLine & vbNewLine & "Partitioned List" & vbNewLine & vbNewLine
Call Partition3(aiData, 0, 7)
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
MsgBox(stOut)
End Sub
Function Partition3(ByRef aiData As Integer(), iLeft As Integer, iRight As Integer)
Dim iTemp As Integer
Do While iLeft <> iRight
Do While (aiData(iLeft) < aiData(iRight)) And (iLeft <> iRight)
iLeft = iLeft + 1
Loop
iTemp = aiData(iLeft)
aiData(iLeft) = aiData(iRight)
aiData(iRight) = iTemp
Do While (aiData(iLeft) < aiData(iRight)) And (iLeft <> iRight)
iRight = iRight - 1
Loop
iTemp = aiData(iLeft)
aiData(iLeft) = aiData(iRight)
aiData(iRight) = iTemp
Loop
Return iLeft
End Function
End Class
Quicksort a list
The code below includes a procedure to call one of the partitioning functions recursively (any one will do), and therefore quicksort the list.
Public Class Form1
Private Sub btnQuickSort_Click(sender As Object, e As EventArgs) Handles btnQuickSort.Click
Dim aiData(7) As Integer
aiData(0) = 5
aiData(1) = 2
aiData(2) = 7
aiData(3) = 6
aiData(4) = 9
aiData(5) = 1
aiData(6) = 4
aiData(7) = 8
Call QuickSort(aiData, 0, 7)
Dim stOut As String
For i As Integer = 0 To 7
stOut = stOut & aiData(i) & " "
Next
MsgBox(stOut)
End Sub
Sub QuickSort(ByRef data As Integer(), left As Integer, right As Integer)
If left < right Then
Dim PivotPosition As Integer = Partition(data, left, right)
QuickSort(data, left, PivotPosition - 1)
QuickSort(data, PivotPosition + 1, right)
End If
End Sub
Function Partition(ByRef aiData As Integer(), iLeft As Integer, iRight As Integer)
Dim iPivot As Integer
iPivot = aiData(iLeft)
Do While iLeft <> iRight
Do While (aiData(iRight) > iPivot) And (iLeft <> iRight)
iRight = iRight - 1
Loop
aiData(iLeft) = aiData(iRight)
Do While (aiData(iLeft) < iPivot) And (iLeft <> iRight)
iLeft = iLeft + 1
Loop
aiData(iRight) = aiData(iLeft)
Loop
aiData(iLeft) = iPivot
Return iLeft
End Function
End Class