Aim

To implement Selection Sort in PHP, printing the array after each selection so the growth of the sorted prefix is visible.

Theory

Selection Sort divides the array into a sorted prefix and an unsorted suffix. On each pass it selects the minimum of the unsorted region and swaps it into the first unsorted slot, growing the sorted prefix by one.

Analytical profile:

• Comparisons: always n(n-1)/2 → O(n²) in best, average and worst case — unlike Bubble Sort with a flag, it cannot exploit pre-sorted input (it is non-adaptive).
• Swaps: at most n − 1 — its distinguishing strength. When writes are expensive (EEPROM/flash memory, huge records), minimising swaps matters.
• Space: O(1), in place.
• Stability: not stable in this classic form — the long-distance swap can jump an element over an equal one (e.g. [5a, 5b, 1] becomes [1, 5b, 5a]).

Contrast for the viva: Bubble Sort does many local swaps and can finish early; Selection Sort does a fixed amount of scanning but the fewest possible swaps.

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 p06b_selection_sort.php in C:\xampp\htdocs\wbplab.
3. Run http://localhost/wbplab/p06b_selection_sort.php or php p06b_selection_sort.php.
4. Add a counter for comparisons and one for swaps, then run sorted, random and reverse-sorted arrays of the same size — observe that comparisons never change while swaps do.

Explanation of the Code

• function selectionSort(array $data): array again takes a copy (value semantics) with typed signature.
• The outer loop index $i marks the first unsorted slot; $minIndex = $i assumes the current element is the minimum.
• The inner loop for ($j = $i + 1; $j < $n; $j++) scans the rest of the unsorted region, updating $minIndex whenever a smaller value $data[$j] < $data[$minIndex] is found — note it only records the index, it does not swap yet.
• After the scan, one list-assignment swap [$data[$i], $data[$minIndex]] = [$data[$minIndex], $data[$i]]; places the minimum; even when $minIndex === $i the self-swap is harmless.
• Each pass prints its state via implode(", ", $data), and main code echoes the original and final arrays.

Expected Output

Original: 7, 5, 4, 2
Step 1: 2, 5, 4, 7
Step 2: 2, 4, 5, 7
Step 3: 2, 4, 5, 7
Selection Sort: 2, 4, 5, 7

Pass 1 swaps 2 with 7; pass 2 swaps 4 with 5; pass 3 finds 5 already minimal.

🎯 Viva Questions

1. How many swaps does Selection Sort perform at most? n − 1 — one per pass, its key advantage.
2. Why is it O(n²) even on sorted input? The full scan for the minimum happens regardless of existing order; it is non-adaptive.
3. Is Selection Sort stable? No — the long-range swap can move an element past an equal element.
4. Role of $minIndex in the code? It defers the swap: the scan only remembers where the minimum is, swapping once per pass.
5. When is Selection Sort a sensible choice? When writes/swaps are far costlier than reads, e.g. flash memory or large records.
6. Compare pass guarantees of Bubble vs Selection. Bubble fixes the largest element at the end each pass; Selection fixes the smallest at the front.

CO Mapping

CO1, CO2