Learn
B2.4.3 | BUBBLE AND SELECTION SORT
01 | SAME DESTINATION, DIFFERENT JOURNEYS
Five quiz scores arrive in the order [5, 1, 4, 2, 3]. We want them in ascending order: [1, 2, 3, 4, 5]. A sorting algorithm must rearrange the existing items without losing any or adding extra ones.
Bubble sort repeatedly compares neighbours and swaps an out-of-order pair. Selection sort scans the remaining candidates for a minimum, then places that minimum at the next sorted position.
This SL/HL lesson constructs and traces both algorithms, then evaluates their comparisons, swaps, time complexity and extra memory. The implementation details matter, especially bubble sort’s early-stop rule.
02 | THE LANGUAGE OF A SORT
| Term | Meaning in this lesson |
|---|---|
| Ascending | Smaller values before larger values; equals are allowed |
| Adjacent | Next to each other, at indexes i and i + 1 |
| Comparison | A data-value order test, such as values[i] > values[i + 1] |
| Swap | Exchange two stored items |
| Pass | One outer-loop iteration through its current candidates |
| Sorted region | Positions guaranteed to be in their final sorted locations |
An index identifies a position; a value is stored at that position. A comparison can lead to a swap, but not every comparison requires one.
We count data-value comparisons separately from swaps. Loop-control tests and other instructions also take time, but are not included in these particular classroom counters.
03 | SWAP WITHOUT LOSING A VALUE
values = [5, 1]
temporary = values[0]
values[0] = values[1]
values[1] = temporary
print(values)
The output is [1, 5]. temporary preserves the old 5 before position 0 is overwritten. Writing values[0] = values[1] followed by values[1] = values[0] would duplicate 1 and lose 5.
Python can write the exchange as values[0], values[1] = values[1], values[0]. The right-hand values are obtained before the assignments overwrite the positions.
A swap exchanges two items. Counting one swap is different from counting every assignment involved in implementing it.
04 | BUBBLE SORT: MOVE A LARGE VALUE RIGHT
Start with [5, 1, 4, 2, 3]. Compare 5 and 1: they are in the wrong order, so swap them. The list becomes [1, 5, 4, 2, 3]. Now compare the new neighbours at indexes 1 and 2: 5 and 4.
Continue moving right, always comparing the current adjacent pair. The largest remaining value moves through the list until it reaches the rightmost active position.
Do not advance an imagined original pair after a swap. Read the list as it exists now: the moved value participates in the next adjacent comparison.
05 | ONE COMPLETE BUBBLE PASS
| Pair indexes | Values before comparison | Action | List after action |
|---|---|---|---|
| 0, 1 | 5, 1 | Swap | [1, 5, 4, 2, 3] |
| 1, 2 | 5, 4 | Swap | [1, 4, 5, 2, 3] |
| 2, 3 | 5, 2 | Swap | [1, 4, 2, 5, 3] |
| 3, 4 | 5, 3 | Swap | [1, 4, 2, 3, 5] |
Pass 1 makes four comparisons and four swaps. The 5 is now guaranteed to be in its final position at index 4. The earlier part is not yet sorted: 4 still precedes 2 and 3.
A completed pass is not necessarily a completed sort. We repeat on the remaining active prefix.
06 | SHORTEN THE ACTIVE PART AFTER EACH PASS
| Stage | List after stage | Guaranteed final suffix |
|---|---|---|
| Initial | [5, 1, 4, 2, 3] | None |
| Pass 1 | [1, 4, 2, 3, 5] | 5 |
| Pass 2 | [1, 2, 3, 4, 5] | 4, 5 |
| Pass 3: no swaps | [1, 2, 3, 4, 5] | All items; stop early |
Pass 2 compares only the first four active items, making three comparisons. Pass 3 checks the first three active items, making two comparisons and no swaps. The optimized algorithm then stops. Total: 9 comparisons and 6 swaps.
The list happens to look sorted after pass 2, but the algorithm has not yet established that no more swaps are needed through its early-stop test. Trace the implemented checks rather than stopping when a human can see the answer.
07 | CONSTRUCT OPTIMIZED BUBBLE SORT
def bubble_sort(values):
for end in range(len(values) - 1, 0, -1):
swapped = False
for index in range(end):
if values[index] > values[index + 1]:
values[index], values[index + 1] = values[index + 1], values[index]
swapped = True
if not swapped:
break
values = [5, 1, 4, 2, 3]
bubble_sort(values)
print(values)
The function modifies values in place and prints [1, 2, 3, 4, 5] through the caller. It has no explicit return, so Python returns None. Do not write values = bubble_sort(values) expecting a sorted list result from this interface.
end is the rightmost active index. range(end) supplies pair-start indexes 0 through end − 1, allowing safe access to index + 1 up to end.
For an empty or one-item list, the outer range is empty and no pair is accessed. Both inputs are already sorted.
08 | THE SWAPPED FLAG MUST RESET EACH PASS
swapped begins False inside the outer loop. Every actual swap sets it True. At the end of the pass, not swapped means that all checked neighbours were already in order, so the active region is sorted.
Together with the previously settled suffix, that gives a sorted whole list. The break exits the outer loop because it is placed after the inner loop, within the outer body.
If swapped is initialized only once before all passes, a swap in pass 1 can leave it True forever, preventing useful early stopping. If it is reset inside every comparison, it may forget an earlier swap and stop too soon.
09 | SELECTION SORT: FIND, THEN PLACE
For selection sort, the sorted region grows from the left. On each pass, find the smallest value in the unsorted suffix, then exchange it with the first unsorted position.
The algorithm does not immediately swap every smaller value it encounters. It remembers the index of the smallest candidate so far and waits until the scan finishes.
For [5, 1, 4, 2, 3], pass 1 finds the minimum 1 at index 1. One swap places it at index 0, producing [1, 5, 4, 2, 3].
10 | TRACE THE MINIMUM CANDIDATE
| Scan action | Candidate compared | minimum_index after action | Minimum value so far |
|---|---|---|---|
| Initialize at start = 0 | No comparison | 0 | 5 |
| Inspect index 1 | 1 < 5 is True | 1 | 1 |
| Inspect index 2 | 4 < 1 is False | 1 | 1 |
| Inspect index 3 | 2 < 1 is False | 1 | 1 |
| Inspect index 4 | 3 < 1 is False | 1 | 1 |
After four comparisons, minimum_index is 1. Only now does the algorithm swap indexes 0 and 1. Remember an index, not only the minimum value, because the swap needs the minimum’s location.
Updating minimum_index is not a swap: no stored list item moves during these comparisons.
11 | SELECTION PASSES GROW A SORTED PREFIX
| Pass | First unsorted index | Chosen minimum | List after final swap |
|---|---|---|---|
| 1 | 0 | 1 | [1, 5, 4, 2, 3] |
| 2 | 1 | 2 | [1, 2, 4, 5, 3] |
| 3 | 2 | 3 | [1, 2, 3, 5, 4] |
| 4 | 3 | 4 | [1, 2, 3, 4, 5] |
After each pass, one more leftmost position is final. The last remaining item needs no separate selection pass because all other positions have been settled.
The comparison counts are 4, 3, 2 and 1, giving 10. This example makes four actual swaps. Other input orders may need fewer swaps, but the shown selection algorithm still performs the same comparisons for the same length.
12 | CONSTRUCT SELECTION SORT
def selection_sort(values):
for start in range(len(values) - 1):
minimum_index = start
for index in range(start + 1, len(values)):
if values[index] < values[minimum_index]:
minimum_index = index
if minimum_index != start:
values[start], values[minimum_index] = values[minimum_index], values[start]
values = [5, 1, 4, 2, 3]
selection_sort(values)
print(values)
The function modifies the supplied list in place. start marks the next position to fill. minimum_index begins at start, and the inner loop visits the later candidates.
Only a smaller candidate changes minimum_index. After the scan, swap only when the minimum is at a different index. This avoids counting or performing an unnecessary self-swap.
Like bubble_sort, this function returns None implicitly. Its effect is the changed list, not a separate returned copy.
13 | ONE INTERACTIVE LAB, TWO ALGORITHMS
Enter up to 10 integers from −99 to 99. Each step shows one comparison, a placement swap or a pass conclusion. Snapshots show the list AFTER the described action, and the compared values before that action are stated in the explanation. Completed passes stay visible below.
Key: COMPARED = inspected this step; MIN = selection candidate; FINAL = settled region; ACTIVE = not yet guaranteed final. Text labels accompany the colours.
Try sorted, reverse-sorted, repeated and negative values. Predict whether the next action changes an item or only the remembered minimum index. Switch algorithms to compare the same original input; changes restart the trace.
14 | KEEP COMPARISONS AND SWAPS SEPARATE
| For input [5, 1, 4, 2, 3] | Bubble sort shown | Selection sort shown |
|---|---|---|
| Data comparisons | 9 | 10 |
| Actual exchanges of different positions | 6 | 4 |
| First final region | Largest value at right | Smallest value at left |
| Can stop after a no-swap pass? | Yes | Not in this implementation |
Bubble sort can exchange many adjacent pairs in one pass. Selection sort exchanges at most one pair per pass, but still scans the whole remaining suffix for its minimum.
Fewer swaps does not automatically mean fewer comparisons or a better asymptotic time class. Evaluate the operations that matter for the scenario.
15 | COUNT THE TRIANGULAR COMPARISONS
For n items, standard selection sort compares n − 1 candidates on the first pass, n − 2 on the next, then continues down to 1. The total is n(n − 1)/2.
For n = 5, the count is 4 + 3 + 2 + 1 = 10. Expanding the formula gives (n² − n)/2, whose dominant term is quadratic. Its standard time classification is O(n²).
Bubble sort without early stopping makes the same triangular number of comparisons with these shrinking bounds. Our optimized version can perform fewer comparisons when its no-swap test ends the process early.
16 | BUBBLE SORT: BEST, AVERAGE AND WORST
For an already sorted list of n ≥ 2 items, the first pass makes n − 1 comparisons and no swaps. The flag stops further passes, giving O(n) best-case time.
A reverse-sorted list of distinct values causes every comparison to swap and requires the full triangular schedule: O(n²) worst-case time and n(n − 1)/2 swaps.
Under the usual uniformly random permutation model for distinct items, average-case time is also O(n²). State the model rather than treating “average” as an unspecified convenient input.
Without the early-stop flag, the shrinking-bound bubble sort has O(n²) time even on sorted input. A complexity statement belongs to a particular algorithm version.
17 | SELECTION SORT: ORDER DOES NOT REMOVE THE SCAN
The shown selection sort always checks the remaining suffix, even if it is already sorted. Its n(n − 1)/2 comparisons give O(n²) best-, average- and worst-case time under constant-time comparisons.
The implementation avoids self-swaps, so a sorted list makes zero actual swaps. An arbitrary input makes at most n − 1 swaps. The exact number depends on input order.
Therefore selection sort can be attractive relative to bubble sort when writes or exchanges are expensive, but both still have quadratic worst-case comparison work and limited scalability.
18 | SPACE: IN PLACE DOES NOT MEAN NO MEMORY
Both shown functions rearrange the existing list using a fixed number of indexes, a flag or a minimum index, and constant-sized swap storage. Their auxiliary space is O(1) in the fixed-size-item model.
The input list itself occupies O(n) storage, but auxiliary space convention excludes that existing input. If a wrapper first copies the list to preserve it, that copy needs O(n) extra space.
The teaching visualizer stores many snapshots to explain the process. Its memory use is not the auxiliary space of the compact sorting functions. Analyse the actual program and the chosen boundary.
19 | EQUAL VALUES AND STABILITY
A stable sort preserves the original relative order of records with equal sort keys. Imagine two students with the same mark: a stable mark sort retains their previous order relative to each other.
Our bubble sort swaps only when the left key is strictly greater than the right. Equal-key neighbours never cross, so it is stable. Replacing > with >= can change that property and also trigger unnecessary swaps.
Standard swap-based selection sort is not stable. For records [2A, 2B, 1], the first pass swaps 1 with 2A, producing [1, 2B, 2A]. The equal-key records A and B have reversed order. A and B label records, not different numerical keys.
20 | JAVA: COMPLETE SORTING METHODS
import java.util.Arrays;
public class SortExample {
static void bubbleSort(int[] values) {
for (int end = values.length - 1; end > 0; end--) {
boolean swapped = false;
for (int index = 0; index < end; index++) {
if (values[index] > values[index + 1]) {
int temporary = values[index];
values[index] = values[index + 1];
values[index + 1] = temporary;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
static void selectionSort(int[] values) {
for (int start = 0; start < values.length - 1; start++) {
int minimumIndex = start;
for (int index = start + 1; index < values.length; index++) {
if (values[index] < values[minimumIndex]) {
minimumIndex = index;
}
}
if (minimumIndex != start) {
int temporary = values[start];
values[start] = values[minimumIndex];
values[minimumIndex] = temporary;
}
}
}
public static void main(String[] args) {
int[] first = {5, 1, 4, 2, 3};
int[] second = {5, 1, 4, 2, 3};
bubbleSort(first);
selectionSort(second);
System.out.println(Arrays.toString(first));
System.out.println(Arrays.toString(second));
}
}
Both outputs are [1, 2, 3, 4, 5]. The void methods mutate their supplied arrays. Separate initial arrays ensure the second algorithm does not receive the already sorted result of the first.
The loop boundaries and strict comparison rules match the Python versions. Trace indexes separately from values in either language.
21 | SORT RECORDS WITHOUT BREAKING THEIR LINKS
def bubble_sort_by_mark(records):
for end in range(len(records) - 1, 0, -1):
swapped = False
for index in range(end):
if records[index]["mark"] > records[index + 1]["mark"]:
records[index], records[index + 1] = records[index + 1], records[index]
swapped = True
if not swapped:
break
records = [{"name": "Ada", "mark": 7},
{"name": "Lin", "mark": 5},
{"name": "Sam", "mark": 7}]
bubble_sort_by_mark(records)
print([record["name"] for record in records])
The output is ['Lin', 'Ada', 'Sam']. Compare marks, but exchange the whole records so names remain attached to the correct marks. Ada stays before Sam because their equal marks never swap.
Sorting only the mark fields while leaving names in their old positions would corrupt the associations. Define the key and move the complete items.
22 | DESCENDING ORDER AND THE COMPARISON RULE
To adapt bubble sort for descending order, swap neighbours when the left value is less than the right. This moves larger values toward the front and settles the smallest remaining value at the right on each left-to-right pass.
To adapt selection sort for descending order, remember the maximum in the unsorted suffix and place it at the next prefix position. Change the candidate test from < to >.
The broad time and auxiliary-space classes remain the same under these changes. The values chosen and the meaning of the final region change, so update trace explanations as well as the operator.
23 | CONSTRUCT TESTS THAT CHECK MORE THAN ORDER
| Test | What to check |
|---|---|
| Empty / one item | No invalid neighbour access; unchanged result |
| Already sorted | Bubble stops after one non-swapping pass for n ≥ 2 |
| Reverse sorted | Many swaps; correct final order |
| Duplicates | Values preserved; required stability respected |
| Negative and zero values | Numerical comparisons handle signs |
| Several passes needed | Correct shrinking bounds and final regions |
Check that the final sequence is ordered and that it contains exactly the same items with the same multiplicities. An algorithm that loses a value can produce a sorted-looking but incorrect result.
Also check the interface: these functions mutate the original and return None. A copy-returning version has a different contract and different extra-space cost.
24 | INVARIANTS AND TERMINATION
After each completed bubble pass, the largest value from that active prefix is settled at its rightmost index. The settled suffix grows and can be excluded from later comparisons.
After each completed selection pass, the prefix contains the required smallest items in their final positions. The remaining minimum is moved into the next position, preserving that property.
The finite loop ranges shrink the active region, guaranteeing termination. Bubble sort may terminate sooner through its flag. A no-swap selection pass does not prove the unsorted suffix is ordered: [1, 3, 2] needs no swap at start 0 but still requires another pass.
25 | EVALUATE THE CHOICE FOR A SCENARIO
For an already sorted or suitably favourable nearly sorted dataset, optimized bubble sort can benefit from early stopping. However, “nearly sorted” does not guarantee linear time: one small item near the end may move left only one position per pass.
Selection sort performs a predictable triangular scan and at most n − 1 exchanges, which can be useful when exchanges are costly. It cannot exploit sorted input to reduce its comparison count in this version.
Both are simple, use O(1) auxiliary space and can suit small educational examples. Both have O(n²) worst-case time, so a suitable O(n log n) sorting algorithm is usually a better scalability choice for large general datasets.
An evaluation should connect the data order, size, stability requirement, comparison/write costs and memory constraints to a justified conclusion, rather than name a universal winner.
26 | TRACE, CONSTRUCT AND EVALUATE CLEARLY
For Trace, follow the supplied version exactly: show each comparison or requested pass, mark the current state and record swaps only when they occur. For selection sort, distinguish a new candidate minimum from an actual placement swap.
For Construct, supply complete initialization, safe loop bounds, correct comparison, swap logic and the promised mutation or return behaviour. Place the bubble flag correctly and selection’s final swap after its scan.
For Evaluate, state time and auxiliary-space complexity for the version and case, then weigh the advantages against the scenario. Explain why a feature matters using because, therefore or resulting in.