Programming technique · B2.4.3
Bubble sort and selection sort
Both algorithms rearrange values into order, but they make progress differently. You need to construct, trace and evaluate both rather than treat sorting as a built-in black box.
Bubble sort: compare neighbours
Bubble sort repeatedly compares adjacent values and swaps an out-of-order pair. After a complete pass, the largest remaining value has moved to the end of the unsorted section.
| First pass from [42, 35, 51, 38, 46] | Action | State |
|---|---|---|
| 42 vs 35 | swap | [35, 42, 51, 38, 46] |
| 42 vs 51 | keep | [35, 42, 51, 38, 46] |
| 51 vs 38 | swap | [35, 42, 38, 51, 46] |
| 51 vs 46 | swap | [35, 42, 38, 46, 51] |
swapped flag allows an already sorted array to stop after one no-swap pass.Selection sort: choose the smallest remaining value
Selection sort scans the unsorted section to remember the smallest value's index, then places that value at the current start position. The sorted prefix grows by one position per pass.
| First pass from [42, 35, 51, 38, 46] | smallestIndex | Reason |
|---|---|---|
| start at index 0 (42) | 0 | initial candidate |
| index 1: 35 | 1 | 35 < 42 |
| index 2: 51 | 1 | 51 is not smaller than 35 |
| index 3: 38 | 1 | 38 is not smaller than 35 |
| index 4: 46 | 1 | 46 is not smaller than 35 |
| place smallest | 1 | swap positions 0 and 1 → [35, 42, 51, 38, 46] |
Check your understanding
Answer each question before opening the model answer.
-
After one bubble-sort pass, what can you say with confidence?
Reveal model answer
The largest value in the section processed by that pass has moved to the end of that unsorted section.
-
What does smallestIndex store during selection sort?
Reveal model answer
The index of the smallest value found so far in the current unsorted section.
-
Why can optimized bubble sort have O(n) best-case time?
Reveal model answer
If the data is already sorted, one pass makes no swaps, so the algorithm stops after a single linear scan.
-
Does selection sort become O(n) on already sorted input?
Reveal model answer
No. It still scans the remaining unsorted section on every pass, so its comparison growth remains O(n^2).
Evaluate rather than declare a winner
| Evidence | Optimized bubble sort | Selection sort |
|---|---|---|
| Best-case time | O(n) after a no-swap pass | O(n^2) comparisons |
| Average/worst time | O(n^2) | O(n^2) |
| Auxiliary space | O(1) | O(1) |
| Value movement | May perform many adjacent swaps | At most one placement swap per outer pass in this model |
| Already/nearly sorted data | Early exit can help | Still scans remaining candidates |
Test the algorithm, not only the final output
Use unsorted, sorted, reverse-order, single-element and empty data. A final sorted result is necessary, but tracing the passes is what proves you understand how the named algorithm achieved it.
Challenges Choose one
Choose a challenge that feels appropriate for you. Code heat is only a rough estimate, not a fixed level.
Build Both Sorts
SelectedConstruct bubbleSort and selectionSort without using library sorting. Test each method with unsorted, already sorted, reverse-order, single-element and empty arrays. Hand-trace at least one complete pass of each algorithm before running the program, then confirm the trace against the code.
Sort Operation Counter
SelectedInstrument both sorting methods with counters for comparisons and swaps. Run the same unsorted, sorted and reverse-order data through both algorithms. Use the evidence to explain optimized bubble sort's O(n) best case, the O(n^2) average/worst growth of bubble sort, selection sort's O(n^2) comparison growth, and O(1) auxiliary space for both in-place models.
Sorting Recommendation
SelectedCreate a small program that can sort the same data with either bubble sort or selection sort. Compare their behaviour on nearly sorted and reverse-order inputs, then write a balanced recommendation for two different scenarios. Your judgement must discuss input order, comparisons, value movement/swaps, time complexity and auxiliary space rather than claiming one algorithm is universally better.
Selected challenge
This choice is shared with the portfolio setup page.
Plan your solution in handwritten pseudocode
Before opening your IDE or writing any program code, handwrite pseudocode for this challenge on paper.
Not marked complete. If you submit now, the GitHub README will record “No”.
Create your challenge folder
Run this command after planning. It creates the correct empty folder inside your portfolio.
Complete the challenge
Use your handwritten pseudocode as the starting plan, then write and test your solution in the folder created above.
Optional two-level scaffold
Try from your handwritten pseudocode first. Scaffold gives some structure; Scaffold + comments gives stronger guidance. Use only the level you need, and update your pseudocode first if the support changes your plan.
Submit for review
Run this when your program is complete. It creates the README, commits the folder and pushes it. The README records whether you marked the handwritten pseudocode as complete; the paper itself is handed to your teacher separately.