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.php 
<?php
function partition(&$arr, $low, $high) {
	$pivot = $arr[$high];
	$i = $low - 1;
	for ($j = $low; $j < $high; $j++) {
		if ($arr[$j] <= $pivot) {
			$i++;
			$tmp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $tmp;
		}
	}
	$tmp = $arr[$i + 1]; $arr[$i + 1] = $arr[$high]; $arr[$high] = $tmp;
	return $i + 1;
}

function quick_sort(&$arr, $low, $high) {
	if ($low < $high) {
		$pivot_index = partition($arr, $low, $high);
		quick_sort($arr, $low, $pivot_index - 1);
		quick_sort($arr, $pivot_index + 1, $high);
	}
}

$arr = [4, 1, 5, 2, 3];
quick_sort($arr, 0, count($arr) - 1);
echo "[" . implode(", ", $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

  • $arr is the pinned PHP array literal [4, 1, 5, 2, 3].
  • quick_sort(&$arr, $low, $high) and partition(&$arr, $low, $high) take $arr by reference, so swaps mutate the same array that is later printed.
  • The pivot is the last slot in the active range: $pivot = $arr[$high].
  • Lomuto's left boundary starts as $i = $low - 1, then $j scans from $low up to $high - 1.
  • The comparison is $arr[$j] <= $pivot; values 1 and 2 move left of pivot 3, while 4 and 5 stay on the right in the first partition trace.
  • Swaps use a temporary variable: $tmp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $tmp;, then the pivot swaps into $i + 1.
  • The replay shows [4, 1, 5, 2, 3] becoming [1, 4, 5, 2, 3], then [1, 2, 5, 4, 3], then [1, 2, 3, 4, 5] when pivot 3 lands at index 2.
  • Recursive calls then cover $low..$pivot_index - 1 and $pivot_index + 1..$high; the trace records left [1, 2] and right [4, 5] already sorted.
  • The final echo concatenates [ + implode(", ", $arr) + ], then closes the quoted string after a literal 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.