Sorting

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 PHP DSA implementation can be compared directly with the other languages.

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) . "]
";

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.