Quick Sort Iterative

Quick sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

									Public Shared Sub QuickSortIterative(ByRef data As Integer())
	Dim startIndex As Integer = 0
	Dim endIndex As Integer = data.Length - 1
	Dim top As Integer = -1
	Dim stack As Integer() = New Integer(data.Length - 1) {}

	stack(System.Threading.Interlocked.Increment(top)) = startIndex
	stack(System.Threading.Interlocked.Increment(top)) = endIndex

	While top >= 0
		endIndex = stack(System.Math.Max(System.Threading.Interlocked.Decrement(top), top + 1))
		startIndex = stack(System.Math.Max(System.Threading.Interlocked.Decrement(top), top + 1))

		Dim p As Integer = Partition(data, startIndex, endIndex)

		If p - 1 > startIndex Then
			stack(System.Threading.Interlocked.Increment(top)) = startIndex
			stack(System.Threading.Interlocked.Increment(top)) = p - 1
		End If

		If p + 1 < endIndex Then
			stack(System.Threading.Interlocked.Increment(top)) = p + 1
			stack(System.Threading.Interlocked.Increment(top)) = endIndex
		End If
	End While
End Sub

Private Shared Function Partition(ByRef data As Integer(), left As Integer, right As Integer) As Integer
	Dim x As Integer = data(right)
	Dim i As Integer = (left - 1)

	For j As Integer = left To right - 1
		If data(j) <= x Then
			i += 1
			Swap(data(i), data(j))
		End If
	Next

	Swap(data(i + 1), data(right))

	Return (i + 1)
End Function

Private Shared Sub Swap(ByRef a As Integer, ByRef b As Integer)
	Dim temp As Integer = a
	a = b
	b = temp
End Sub

Example

									Dim data() As Integer = { -1, 25, -58964, 8547, -119, 0, 78596 }
QuickSortIterative(data)

Output