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.R 
partition <- function(arr, low, high) {
	pivot <- arr[high]
	i <- low - 1
	for (j in low:(high - 1)) {
		if (arr[j] <= pivot) {
			i <- i + 1
			tmp <- arr[i]; arr[i] <- arr[j]; arr[j] <- tmp
		}
	}
	tmp <- arr[i + 1]; arr[i + 1] <- arr[high]; arr[high] <- tmp
	list(arr = arr, pivot = i + 1)
}

quick_sort <- function(arr, low, high) {
	if (low < high) {
		part <- partition(arr, low, high)
		arr <- part$arr
		pivot_index <- part$pivot
		arr <- quick_sort(arr, low, pivot_index - 1)
		arr <- quick_sort(arr, pivot_index + 1, high)
	}
	arr
}

arr <- quick_sort(c(4, 1, 5, 2, 3), 1, 5)
cat("[", paste(arr, collapse = ", "), "]
", sep = "")

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

  • The checked input is the R vector c(4, 1, 5, 2, 3).
  • quick_sort(arr, low, high) returns the sorted vector; the source reassigns arr after partitioning and after each recursive call.
  • R vector indexes are 1-based, so the top-level call is quick_sort(..., 1, 5).
  • partition(arr, low, high) chooses the last slot as the pivot: pivot <- arr[high], so the first pivot is 3.
  • i <- low - 1 starts at 0 for the first partition.
  • The comparison loop is for (j in low:(high - 1)), so this run checks R indexes 1 through 4.
  • The condition is arr[j] <= pivot; values less than or equal to the pivot move to the left side.
  • Swaps use a temporary scalar: tmp <- arr[i]; arr[i] <- arr[j]; arr[j] <- tmp.
  • Final pivot placement also uses tmp, swapping arr[i + 1] with arr[high].
  • partition returns list(arr = arr, pivot = i + 1), and quick_sort unpacks that with part$arr and part$pivot.
  • The trace reports zero-based partition labels, so its j=0 corresponds to R index 1, and its final pivot index 2 corresponds to R index 3.

First partition replay

start:             [4, 1, 5, 2, 3], pivot = 3
compare 4 <= 3:   [4, 1, 5, 2, 3]
compare 1 <= 3:   [1, 4, 5, 2, 3]
compare 5 <= 3:   [1, 4, 5, 2, 3]
compare 2 <= 3:   [1, 2, 5, 4, 3]
place pivot 3:    [1, 2, 3, 4, 5]
  • The replay then summarizes the left side [1, 2] and right side [4, 5], both already sorted after the first pivot lands.
  • The final cat call combines "[", paste(arr, collapse = ", "), and a closing bracket string that contains the newline, so it prints [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.