Bubble Sort and Selection Sort
Construct and trace both sorting algorithms, then evaluate their time, space and practical trade-offs.
What you need to be able to do
- construct and trace bubble sort without relying on a built-in sort;
- construct and trace selection sort;
- state and interpret the time and auxiliary-space complexities of both algorithms;
- evaluate advantages and disadvantages across different data sets.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
Trace one full pass
[5, 2, 4, 1]. Sort into ascending order.Trace pass 1
Bubble sort compares adjacent pairs from left to right and swaps when the left value is larger.
- 5 and 2 → swap:
[2, 5, 4, 1] - 5 and 4 → swap:
[2, 4, 5, 1] - 5 and 1 → swap:
[2, 4, 1, 5]
After pass 1, the largest value 5 is in its final position.
Write the algorithm manually
sort() or sorted().Construct bubble_sort(data)
def bubble_sort(data):
n = len(data)
for end in range(n - 1, 0, -1):
swapped = False
for j in range(end):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
swapped = True
if not swapped:
break
return dataSelect the minimum remaining item
[5, 2, 4, 1]. Sort into ascending order.Trace the first two passes
Pass 1: minimum is 1 at index 3; swap with index 0 → [1, 2, 4, 5]. Pass 2: minimum of the remaining region is already 2 at index 1, so the List remains [1, 2, 4, 5].
Keep a sorted and unsorted region
Construct selection_sort(data)
def selection_sort(data):
n = len(data)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return dataSame order of growth, different behaviour
Bubble sort
Worst/average time: O(n²).
Best case with early exit: O(n) when a pass finds no swaps.
Auxiliary space: O(1) for an in-place version.
Can perform many swaps, but can benefit from data that is already or nearly sorted.
Selection sort
Time: O(n²) because it repeatedly scans the unsorted region.
Auxiliary space: O(1) for an in-place version.
Usually performs fewer swaps than bubble sort, but still does roughly quadratic comparisons even when the List starts sorted.
Evaluate for a nearly sorted small List
Which feature could make the early-exit bubble sort attractive, and what limitation still matters?
If the List is already or almost sorted, bubble sort with an early-exit flag may finish after very few passes and can detect a no-swap pass. However, its general worst-case time remains O(n²), so it is not a scalable choice for large unsorted inputs.
Teacher-created Paper 2 practice
1. Trace the first bubble-sort pass on [3, 1, 4, 2].
2. Trace the first selection-sort pass on the same List.
3. Evaluate one advantage of selection sort over bubble sort and one advantage of an early-exit bubble sort over selection sort.
- 3/1 swap →
[1,3,4,2]; 3/4 no swap; 4/2 swap →[1,3,2,4]. - The minimum value is 1 at index 1; swap it with the value at index 0 →
[1,3,4,2]. - Selection sort typically uses fewer swaps because it places one selected minimum per outer pass. Early-exit bubble sort can terminate quickly when the data is already sorted or becomes sorted before all planned passes are complete.
Finish the learning cycle
IA — main task
Review any IA code that orders or ranks data. If sorting is needed, record whether the implementation relies on a library or on a custom algorithm and why that is appropriate for the product.
Syllabus — short retrieval
Redo both first-pass traces on page 9, then explain aloud why two O(n²) algorithms can still have different practical behaviour.