Aim

To implement recursive Quick Sort in PHP with first-element pivoting, printing every partition step to expose the divide-and-conquer structure.

Theory

Quick Sort is a divide-and-conquer algorithm: pick a pivot, partition the remaining elements into those ≤ pivot (left) and those > pivot (right), recursively sort both sides, and concatenate left + pivot + right. The pivot is in its final position after partitioning — that is the invariant driving correctness.

Analysis:

• Average case: O(n log n) — balanced partitions halve the problem, giving log n levels of O(n) partitioning work.
• Worst case: O(n²) — every partition is maximally lopsided. With first-element pivoting (used here), an already-sorted or reverse-sorted array triggers exactly this. Mitigations: random pivot, median-of-three, or introsort's depth-limited fallback to heapsort.
• Space: this functional implementation allocates new $left/$right arrays — O(n) extra per level — favouring clarity; the classic Lomuto/Hoare versions partition in place with O(log n) stack only.
• Stability: not stable in the standard in-place form.
• PHP's own sort() family is a C-level quicksort/introsort hybrid — this practical shows what it does under the hood.

Requirements

• XAMPP/WAMP with PHP 8.x, or PHP CLI
• Code editor; browser or terminal

Procedure

1. Start Apache from the XAMPP Control Panel.
2. Save the snippet as p06d_quick_sort.php in C:\xampp\htdocs\wbplab.
3. Run http://localhost/wbplab/p06d_quick_sort.php or php p06d_quick_sort.php.
4. Feed a sorted array ([1,2,3,4,5]) and watch every right partition come out empty — the O(n²) degenerate case in action.
5. Count the printed partition lines for different inputs to estimate recursion depth.

Explanation of the Code

• function quickSort(array $data): array is recursive; the base case if (count($data) < 2) return $data; terminates recursion on empty/single-element arrays.
• $pivot = $data[0]; chooses the first element; the loop starting at $i = 1 distributes the rest: values <= $pivot are appended to $left[], larger ones to $right[] (using <= puts duplicates of the pivot on the left, preventing infinite recursion on repeated values).
• The echo "Pivot: ..." line prints the pivot with both partitions via implode — reading these lines top-to-bottom reconstructs the recursion tree in depth-first order.
• return array_merge(quickSort($left), [$pivot], quickSort($right)); sorts both halves recursively and stitches the result together; the pivot needs no further work.

Expected Output

Original: 19, 17, 15, 12, 16, 18, 4, 11, 13
Pivot: 19 | Left: [17,15,12,16,18,4,11,13] | Right: []
Pivot: 17 | Left: [15,12,16,4,11,13] | Right: [18]
...
Quick Sort: 4, 11, 12, 13, 15, 16, 17, 18, 19

Because 19 is the maximum, the very first partition is fully lopsided — a live demonstration of first-pivot weakness.

🎯 Viva Questions

1. What is the partition invariant? After partitioning, the pivot occupies its final sorted position; left holds ≤ pivot, right holds > pivot.
2. Average and worst-case complexity? O(n log n) average; O(n²) when partitions are consistently unbalanced.
3. Which inputs are worst for first-element pivoting? Already-sorted or reverse-sorted arrays.
4. How do production quicksorts dodge the worst case? Random or median-of-three pivots, or introsort's switch to heapsort past a depth limit.
5. Why does this version use <= for the left partition? So pivot duplicates land in a partition and recursion still shrinks — avoiding infinite recursion on equal values.
6. Is this implementation in place? No — it builds new $left/$right arrays and merges; classic Lomuto/Hoare partitioning is in place.

CO Mapping

CO1, CO2