Quick Sort (Lomuto)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this R DSA implementation can be compared directly with the other languages.

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 = "")

Complexity

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

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

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.