The big idea: Two simple sorts put a list in order by repeated compares and swaps.
Bubble sort
- Compares neighbouring pairs.
- Swaps them when they are the wrong way round.
- The largest value moves to the end each pass.
Selection sort
- Finds the smallest value in what is left.
- Swaps it into place.
- Once per position.
Both algorithms on the same six numbers, with running comparison and swap counts. Switch between them.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
def bubble_sort(items):
n = len(items)
for pass_no in range(n - 1):
swapped = False
for k in range(n - 1 - pass_no): # the sorted tail shrinks the range
if items[k] > items[k + 1]:
items[k], items[k + 1] = items[k + 1], items[k]
swapped = True
if not swapped:
break # already sorted — stop early
return itemsstatic int[] bubbleSort(int[] items) {
int n = items.length;
for (int passNo = 0; passNo < n - 1; passNo++) {
boolean swapped = false;
for (int k = 0; k < n - 1 - passNo; k++) { // the sorted tail shrinks the range
if (items[k] > items[k + 1]) {
int temp = items[k];
items[k] = items[k + 1];
items[k + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break; // already sorted — stop early
}
}
return items;
}What one pass does
Compare each neighbouring pair along the list, swapping any that are out of order.
The largest value meets every comparison on its way and ends up at the far end — which is why it is called bubbling.
Why the range shrinks
After one pass the last item is final; after two, the last two are.
So each pass needs one comparison fewer — n - 1 - passno is exactly that.
The early exit
If a whole pass makes no swaps, the list is already sorted and there is nothing left to do.
That is what gives bubble sort a best case of O(n) on already-sorted data — one pass to confirm it.
The cost
O(n²) comparisons and O(n²) swaps in the worst case, with O(1) space since it sorts in place.
All those swaps are its real weakness.
Practice with exam-style questions
Answer exam-style questions and get AI feedback that shows you exactly what examiners want to see in a full-marks response.
def selection_sort(items):
n = len(items)
for pos in range(n - 1):
smallest = pos
for k in range(pos + 1, n):
if items[k] < items[smallest]:
smallest = k # remember where, do not swap yet
if smallest != pos:
items[pos], items[smallest] = items[smallest], items[pos]
return itemsstatic int[] selectionSort(int[] items) {
int n = items.length;
for (int pos = 0; pos < n - 1; pos++) {
int smallest = pos;
for (int k = pos + 1; k < n; k++) {
if (items[k] < items[smallest]) {
smallest = k; // remember where, do not swap yet
}
}
if (smallest != pos) {
int temp = items[pos];
items[pos] = items[smallest];
items[smallest] = temp;
}
}
return items;
}Bubble sort
- O(n²) comparisons, O(n²) swaps
- Best case O(n) — one pass over sorted data with the early exit
- Very many swaps: it moves data constantly
- Slightly simpler to write and to trace
Selection sort
- O(n²) comparisons, but only O(n) swaps
- No best case — it always does every comparison
- At most one swap per position, decided after looking
- Better when moving data is what costs
The distinction that matters: Both do O(n²) comparisons. The difference is the swaps.
Selection sort looks first and moves once. Bubble sort moves as it goes. When writing data is expensive, that difference is the whole argument.
Both use O(1) space: Each sorts in place, needing only a couple of extra variables however large the list.
So in a question about memory, neither has an advantage — the answer is that both are O(1).
How this is tested — you must trace a pass exactly and compare on both comparisons and swaps. It comes up two ways:
Paper 2 — working with code
- Trace one or more passes of a sort, 4-6 marks
- State and justify time and space complexity
- Compare the two for a given data set
Paper 2 — the algorithmic-thinking question
- Reason about pass counts with no code shown
- Explain which sort suits a stated situation
The classic trap: Saying selection sort is more efficient. Both do O(n²) comparisons — selection sort only wins on swaps. Saying which measure you mean is the mark.
Show the list after each pass of a bubble sort on [5, 2, 8, 1], then state the complexity and compare with selection sort.
Model answer plan
See the answer broken into clear points, with guidance on how each point earns marks.