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.scala 
object Main {
	def partition(arr: Array[Int], low: Int, high: Int): Int = {
		val pivot = arr(high)
		var i = low - 1
		for (j <- low until high) {
			if (arr(j) <= pivot) {
				i = i + 1
				val tmp = arr(i); arr(i) = arr(j); arr(j) = tmp
			}
		}
		val tmp = arr(i + 1); arr(i + 1) = arr(high); arr(high) = tmp
		i + 1
	}

	def quickSort(arr: Array[Int], low: Int, high: Int): Unit = {
		if (low < high) {
			val pivotIndex = partition(arr, low, high)
			quickSort(arr, low, pivotIndex - 1)
			quickSort(arr, pivotIndex + 1, high)
		}
	}
	def main(args: Array[String]): Unit = {
		val arr = Array(4, 1, 5, 2, 3)
		quickSort(arr, 0, arr.length - 1)
		println(arr.mkString("[", ", ", "]"))
	}
}

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

  • val arr = Array(4, 1, 5, 2, 3) fixes the Scala Array[Int] reference, but partition and quickSort mutate its slots in place.
  • partition(arr: Array[Int], low: Int, high: Int): Int chooses the last slot with val pivot = arr(high).
  • var i = low - 1 marks the end of the left side. The scan for (j <- low until high) uses Scala's exclusive until, so j visits 0, 1, 2, and 3 while the pivot stays at index 4.
  • When arr(j) <= pivot, the code increments i and performs an explicit temporary-variable swap: val tmp = arr(i); arr(i) = arr(j); arr(j) = tmp.
  • The first partition compares against pivot 3: 4 stays right, 1 swaps left to make [1, 4, 5, 2, 3], 5 stays right, and 2 swaps left to make [1, 2, 5, 4, 3].
  • After the scan, a second explicit tmp swap moves the pivot into i + 1, producing [1, 2, 3, 4, 5] with pivot index 2.
  • quickSort recurses only when low < high; the replay then summarizes the already-sorted left side [1, 2] and right side [4, 5].
  • println(arr.mkString("[", ", ", "]")) prints the final array exactly as [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.