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
Write your first version by hand
Before opening your IDE, write your first attempt at this program on paper using Java. It does not need to be perfect.
TASK_CODE
Not marked complete. Mark it complete when your handwritten code is ready.
Open the challenge
Code Companion Local creates the starter file in the exact managed challenge folder and opens it in your preferred IDE. You do not need to create folders, files or run terminal commands.
Mark your handwritten code complete first.
If you are simply browsing the public course and are not using a class, complete the challenge in any editor you like. Code Companion Local is only needed for the connected classroom workflow.
Complete the challenge
Use your handwritten code as the starting point, then write and test your solution in the challenge workspace. Code Companion Local will ask you to compare the two versions before you submit.
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.