Sorting

Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.swift 
func partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
	let pivot = arr[high]
	var i = low - 1
	for j in low..<high {
		if arr[j] <= pivot {
			i += 1
			arr.swapAt(i, j)
		}
	}
	arr.swapAt(i + 1, high)
	return i + 1
}

func quickSort(_ arr: inout [Int], _ low: Int, _ high: Int) {
	if low < high {
		let pivotIndex = partition(&arr, low, high)
		quickSort(&arr, low, pivotIndex - 1)
		quickSort(&arr, pivotIndex + 1, high)
	}
}

var arr = [4, 1, 5, 2, 3]
quickSort(&arr, 0, arr.count - 1)
print(arr)

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

  • Time: O(n^2) worst, O(n log n) average
  • Space: O(log n) average call stack
  • Stable: no

Implementation notes

  • partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int mutates the caller's Swift [Int] through inout; quickSort(&arr, 0, arr.count - 1) passes the same array variable by inout. Swift Array is a value type with copy-on-write storage, and this source mutates it through swapAt without explicitly allocating a replacement array.
  • The pivot is let pivot = arr[high], so each partition uses the current high-bound element as an immutable Int comparison value.
  • var i = low - 1 tracks the last slot on the left side, while for j in low..<high scans only the elements before the pivot.
  • Values satisfying arr[j] <= pivot increment i and call arr.swapAt(i, j); after the scan, arr.swapAt(i + 1, high) places the pivot and returns i + 1.
  • quickSort recurses only when low < high, then calls the left range low...pivotIndex - 1 and right range pivotIndex + 1...high.
  • The trace starts from [4, 1, 5, 2, 3]: comparing 4 and 5 against pivot 3 leaves them on the right, while 1 and 2 swap left to produce [1, 2, 5, 4, 3].
  • The pivot swap moves 3 into index 2, yielding [1, 2, 3, 4, 5]; the replay then records already-sorted left [1, 2] and right [4, 5] recursions.
  • print(arr) uses Swift's array display form and outputs [1, 2, 3, 4, 5].
pivot The final element is moved to the boundary between smaller and larger values.
partition One scan rearranges the current range before the recursive calls.