Aim

To implement Bubble Sort in PHP with the early-exit (swapped-flag) optimisation, printing the array after every pass to visualise how large values "bubble" to the end.

Theory

Bubble Sort repeatedly scans the array, comparing adjacent pairs and swapping them when out of order. After pass i, the i-th largest element is guaranteed to sit in its final position at the right end, so each pass can stop one element earlier ($n - $i - 1).

Complexity analysis:

• Worst / average case: O(n²) comparisons and swaps (reverse-sorted input is worst).
• Best case with the swapped flag: O(n) — one clean pass over already-sorted data detects zero swaps and terminates. Without the flag, even sorted input costs O(n²).
• Space: O(1) auxiliary — sorting is in place.
• Stability: stable, because equal elements are never swapped past each other (the comparison is strictly >).

Properties worth citing in a viva: it is an exchange sort, adaptive only with the flag, and useful in practice solely for tiny or nearly-sorted datasets — production PHP code uses sort()/usort(), which implement introsort-class algorithms in C.

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 p06a_bubble_sort.php in C:\xampp\htdocs\wbplab.
3. Run http://localhost/wbplab/p06a_bubble_sort.php or php p06a_bubble_sort.php.
4. Feed it a sorted array ([1, 2, 3, 4]) and confirm it stops after a single pass — proof the flag works.
5. Feed a reverse-sorted array and count the passes for the worst case.

Explanation of the Code

• function bubbleSort(array $data): array uses parameter and return type declarations; $data arrives as a copy (PHP arrays are value types), so the original $arr is preserved.
• The outer loop for ($i = 0; $i < $n - 1; $i++) performs at most n - 1 passes; $swapped = false resets the flag each pass.
• The inner loop runs to $n - $i - 1, skipping the already-settled suffix. When $data[$j] > $data[$j + 1], the neighbours are exchanged with list assignment: [$data[$j], $data[$j + 1]] = [$data[$j + 1], $data[$j]]; — PHP's idiomatic swap without a temporary variable.
• echo "Step ..." prints the array via implode(", ", $data) after each pass, exposing the algorithm's state.
• if (!$swapped) break; is the early exit: a pass with zero swaps proves the array is sorted.

Expected Output

Original: 5, 3, 8, 4, 6
Step 1: 3, 5, 4, 6, 8
Step 2: 3, 4, 5, 6, 8
Step 3: 3, 4, 5, 6, 8
Bubble Sort: 3, 4, 5, 6, 8

Step 3 shows no change — the flag detects this and the loop breaks.

🎯 Viva Questions

1. Why is it called Bubble Sort? The largest remaining element "bubbles up" to the end of the unsorted region each pass.
2. What does the $swapped flag optimise? Best case drops from O(n²) to O(n) for already-sorted input.
3. Why does the inner loop end at $n - $i - 1? The last $i positions already hold their final values.
4. Is Bubble Sort stable? Why? Yes — equal neighbours are not swapped because the test is strict >.
5. Worst-case input and complexity? Reverse-sorted array; O(n²) comparisons and swaps.
6. What PHP feature swaps without a temp variable? List (array destructuring) assignment: [$a, $b] = [$b, $a].

CO Mapping

CO1, CO2