B2.4.3 · Programming algorithms
Bubble sort and selection sort
Two different ways to put a list in order. Both end up at the same sorted result, on the same data they don't do the same amount of work to get there.
Explainer
A teacher has 5 quiz scores in the order they were handed in and wants them sorted from lowest to highest before recording them. There's more than one sensible way to physically do that, and each one turns into a different sorting algorithm.
Sorting means arranging the elements of a list into ascending or descending order. Bubble sort and selection sort both do this, using genuinely different strategies.
Explainer
Bubble sort: compare neighbours, swap, repeat
Bubble sort compares each pair of adjacent elements, swapping them if they're in the wrong order, then moves on to the next pair. One full pass through the list settles the largest remaining value into its correct position at the end, the same way the biggest bubble always rises to the top first.
Because each pass guarantees one more element at the end is now correctly placed, the next pass never needs to check that far, it can stop one position earlier every time.
Two nested loops, each up to n long: time complexity O(n²). Only a temporary variable is needed to hold a value during a swap, nothing that grows with the list: space complexity O(1).
Explainer
Stopping early with a flag
If an entire pass completes with no swaps at all, the list is already sorted, there's no point continuing. A boolean flag tracks this.
The loop's own exit condition is the flag itself, not a fixed count. If a pass genuinely makes zero swaps, swapped stays False and the while loop ends right there.
A stray break dropped inside the inner for loop is not the same thing, and markers don't accept it as demonstrating early termination. The structure has to genuinely use the flag as the outer loop's own condition, the way it's written above.
This gives bubble sort a real best case of O(n), on data that's already sorted, exactly one pass confirms it and stops. Selection sort, below, has no equivalent, it can never do better than O(n²), no matter how sorted the data already is.
Explainer
Selection sort: find the smallest, put it in place
Selection sort splits the list into a sorted part (empty at first) and an unsorted part (everything, at first). Each pass finds the smallest value in the unsorted part and swaps it into the very next sorted position, growing the sorted part by exactly one each time.
Selection sort makes at most one swap per pass, and it always makes exactly one, whether the list is a mess or almost sorted already. There's no flag, no early-exit condition, it always scans the entire remaining unsorted part to be certain it has found the true minimum before it can move on.
Same shape as bubble sort: two nested loops give time complexity O(n²), and only a couple of tracking variables give space complexity O(1).
Explainer
Comparing them properly
Same worst-case time complexity, same space complexity, but genuinely different behaviour depending on the data.
Real example: a short list of daily temperature readings that's already almost in order, one flag-checked pass confirms it and stops.
Advantage
- Best case O(n) (the swapped flag lets it finish in one pass on already-sorted or nearly-sorted data)
Disadvantage
- Many more swaps on average (every out-of-order adjacent pair triggers its own swap, which adds up across a badly shuffled list)
Real example: sorting a list of large student records, where swapping is expensive because it means copying a whole record, not just a number.
Advantage
- Minimum possible number of swaps (at most one per pass, n-1 in total, valuable when each swap itself is costly)
Disadvantage
- Always the full O(n²) (no way to detect or benefit from data that's already sorted, every pass scans the entire remaining unsorted part regardless)
Worked example
Tracing a bubble sort
Five quiz scores, handed in out of order: 42, 17, 35, 8, 29.
Pass 1. Compare every adjacent pair from the start: (42,17) swap, (42,35) swap, (42,8) swap, (42,29) swap. 42 "bubbles" all the way to the end.
Pass 2. Position 4 (42) is already correct, so this pass only checks up to position 2: (17,35) no swap, (35,8) swap, (35,29) swap.
Pass 3. Positions 3 and 4 are settled. Check up to position 1: (17,8) swap, (17,29) no swap.
Pass 4. Only position 0 vs 1 left to check: (8,17), already in order.
Try it yourself
Run both sorts on the same list
Both functions sort the identical starting list and count their own swaps. Change scores to any list of numbers and press Run to compare the swap counts on different data.
Running in offline fallback mode. The full Python engine couldn't load (blocked school network, or no internet), so this console switched automatically to a small hand-written engine. It supports this page's loops and functions, but it isn't full Python.
Worked example
Tracing a selection sort, same starting list
The exact same 5 scores, sorted with selection sort's find-the-minimum strategy instead.
| Pass | Unsorted part searched | Minimum found | Swapped with | List after |
|---|---|---|---|---|
| 1 | 42, 17, 35, 8, 29 | 8 (position 3) | position 0 (42) | 8, 17, 35, 42, 29 |
| 2 | 17, 35, 42, 29 | 17 (position 1) | position 1 (itself, no real change) | 8, 17, 35, 42, 29 |
| 3 | 35, 42, 29 | 29 (position 4) | position 2 (35) | 8, 17, 29, 42, 35 |
| 4 | 42, 35 | 35 (position 4) | position 3 (42) | 8, 17, 29, 35, 42 |
The exact same final order as bubble sort, 8, 17, 29, 35, 42, reached with only 3 real swaps (pass 2's "swap" changes nothing, since 17 was already in the right place) against bubble sort's 7, on the identical starting data. This is exactly what "selection sort makes fewer swaps" looks like as real numbers, not just a claim.
Check your understanding
Both algorithms are run on a list of 5 numbers that happens to already be fully sorted. Which statement is true?
Common mistake
RecurringWhen asked to compare the two algorithms, a common answer states that they are similar because "both are sorting algorithms" without any further technical detail, or names a difference too vaguely to earn credit.
Vague: "Both are sorting algorithms. Selection sort is a bit more efficient." True, but says nothing about how or why, and could be written without understanding either algorithm at all.
Specific: "Both use two nested loops and have the same O(n²) worst-case time complexity. They differ in swap behaviour: selection sort makes at most one swap per pass, while bubble sort swaps every time an adjacent pair is out of order, and only bubble sort can exit early via a swapped flag if the data is already sorted." Names the real shared property (nested loops, same worst-case complexity) and the real, specific differences (swap count, early-exit capability).
Revision questions
Past-paper style. Write an answer, then reveal the marking points and mark yourself.
[2]State the time and space complexity of both bubble sort and selection sort.
Marking points
评分要点
- Bubble sort: time complexity O(n squared), space complexity O(1).
- Selection sort: time complexity O(n squared), space complexity O(1).
- 冒泡排序:时间复杂度 O(n 平方),空间复杂度 O(1)。
- 选择排序:时间复杂度 O(n 平方),空间复杂度 O(1)。
[3]Explain why bubble sort can achieve a best-case time complexity of O(n), but selection sort cannot.
Marking points
评分要点
- Bubble sort can stop early: if a whole pass makes no swaps the list is already sorted, giving O(n) on sorted input.
- Selection sort always scans the entire unsorted portion to find the minimum on every pass, regardless of the order.
- So selection sort does the same number of comparisons even on already-sorted data, and cannot beat O(n squared).
- 冒泡排序可以提前停止:如果一整趟没有交换,列表就已排好序,对已排序输入给出 O(n)。
- 选择排序在每一趟都扫描整个未排序部分来找最小值,无论顺序如何。
- 所以选择排序即便对已排序的数据也做同样次数的比较,无法优于 O(n 平方)。
[4]A program repeatedly sorts a list of 1000 large records, where swapping two records is a slow operation, but the list only ever needs a handful of elements moved each time (it's nearly sorted already before each sort). Evaluate which algorithm, bubble sort or selection sort, is more appropriate here, justifying your answer.
Marking points
评分要点
- Swapping records is the expensive operation here, so the number of swaps matters more than the number of comparisons.
- Selection sort performs at most n-1 swaps in total, one per pass.
- Bubble sort can perform many swaps, one for every out-of-order adjacent pair, which is costly when each swap is slow.
- However, the list is nearly sorted, so bubble sort with early termination would do very few passes and few swaps.
- A reasonable answer: selection sort bounds the swap count regardless of order; bubble sort is competitive only because the list is nearly sorted, so either can be justified with the trade-off stated.
- 这里交换记录是代价高的操作,所以交换次数比比较次数更重要。
- 选择排序总共最多做 n-1 次交换,每趟一次。
- 冒泡排序可能做很多次交换,每个逆序的相邻对一次,当每次交换都慢时代价很高。
- 不过列表近乎有序,所以带提前终止的冒泡排序只做很少几趟、很少几次交换。
- 合理的答案:选择排序无论顺序如何都限定了交换次数;冒泡排序只因列表近乎有序才有竞争力,所以只要说清权衡,两者都可论证。
Flashcards
Active recall for this statement’s key terms.
Keep this statement’s practice with you
Free account: unlock every revision question and flashcard for B2.4.3, and every other IB CS 2027 statement.