Python Hub - Master CIE A-Level 9618 Python Programming

14.1 How Bubble Sort Works

Bubble sort works in passes. In each pass it walks along the list and, for every pair of neighbouring values, asks one simple question: is the left value bigger than the right value? If yes, the pair is in the wrong order for an ascending sort, so the two values are swapped. If no, the pair is left alone.

Key idea:

After each pass the largest remaining value "bubbles" up to the end of the list.
After pass k, the largest k values are guaranteed to be in their final positions.
The list is fully sorted when a complete pass produces no swaps.

Exam tip:

When a question says "Describe how a bubble sort places the data in order. Do not use pseudocode statements", the marks are for the ideas.
Required ideas: compare adjacent values, swap if in the wrong order, repeat in passes, largest value moves to the end each pass, stop when a pass has no swaps.
Writing code when the question forbids it earns zero.

Knowledge Check 1

How Bubble Sort Works

14.1B Interactive Simulator

Try the bubble sort yourself. Change the array values, then click Start. Use Step for manual control or Play for auto-run. Watch how neighbouring values are compared (rose) and swapped (amber), with sorted elements turning green at the end.

Interactive Simulator

Array:

Simulation

Status: Click Start to begin.

Code

1n = len(numbers)
2for p in range(n - 1):
3    for i in range(n - 1):
4        if numbers[i] > numbers[i+1]:
5            temp = numbers[i]
6            numbers[i] = numbers[i+1]
7            numbers[i+1] = temp
8# sorted!

Speed:

14.2 Bubble Sort in Python — the Standard Version

The standard bubble sort uses only skills you already have — a list, two for loops, an if statement and a swap. Here is the exam-style implementation:

def bubble_sort(numbers):
    n = len(numbers)
    for p in range(n - 1):       # outer loop: one repeat per pass
        for i in range(n - 1):   # inner loop: walk along the neighbours
            if numbers[i] > numbers[i + 1]:
                temp = numbers[i]           # three-line swap with a
                numbers[i] = numbers[i + 1] # temporary variable
                numbers[i + 1] = temp
    return numbers

Why three lines for the swap?

Because if you wrote numbers[i] = numbers[i + 1] first, the original value of numbers[i] would be overwritten and lost forever.
The temporary variable temp keeps a copy safe while the exchange happens.
Cambridge expects this explicit three-line swap.

Key rule — range(n-1), never range(n):

The inner loop runs range(n - 1) times, never range(n), because the comparison reaches one index ahead (i + 1).
Getting this range wrong is the single most common way to lose marks (or crash) in a bubble sort.

Your Turn — Sort quiz scores [4 marks]

Naib stores quiz scores in a Python list. Write a function bubble_sort(scores) that uses bubble sort to arrange scores in ascending order and returns the sorted list. Sort [34, 12, 45, 8, 27] and print the result.

Hint:

Two nested for loops, both range(n-1)
Compare scores[i] > scores[i+1]
Three-line swap with temp
Return the sorted list

Your Turn — Sort in descending order

Write a function bubble_sort_desc(temps) that sorts temperatures in DESCENDING order (highest first). Sort [31, 28, 35, 29, 33, 30, 27].

Hint:

Same two-loop structure
Change the comparison from > to <
Swap when the left value is SMALLER than the right

Your Turn — Sort names alphabetically

Write a bubble sort that arranges student names in alphabetical order. Sort ["Nawal", "Aymaan", "Mohar"].

Hint:

String comparison with > works alphabetically in Python
Same structure — just the data type changes

Your Turn — Count the swaps

Write a function bubble_sort_count(numbers) that sorts the list and also counts how many swaps are made. Print the swap count. Test on [9, 4, 7, 1].

Hint:

Set a counter to 0 before the loops
Add 1 inside the if block, after the swap

Knowledge Check 2

Standard Implementation

14.3 Tracing Bubble Sort

A bubble sort trace records every comparison, whether it swaps or not. The discipline is simple: write down the pair being compared, decide swap or no swap, then write the full list after that comparison.

Your Turn — Trace [5, 3, 8, 2] [6 marks]

Trace a bubble sort, in ascending order, on the list [5, 3, 8, 2]. Show every comparison in every pass.

Hint:

4 values means 3 comparisons per pass
Pass 1: (5,3) swap, (5,8) no, (8,2) swap
Pass 2: (3,5) no, (5,2) swap, (5,8) no
Pass 3: (3,2) swap, then no more swaps needed

Your Turn — Trace [6, 1, 4, 2]

Trace a bubble sort, in ascending order, on the list [6, 1, 4, 2]. Show every comparison in every pass and state the final sorted list.

Hint:

Four values means three comparisons per pass
Keep going until a pass would make no swaps
Pass 3 should have no swaps — confirming sorted

Exam tip:

In a trace, marks are lost for missing rows far more often than for wrong swaps.
Show every comparison — including ones that make no swap — and copy the full list state on every row.
Neat, complete, mechanical tracing earns the marks.

Knowledge Check 3

Tracing & Optimised Version

14.4 Optimised Bubble Sort — the Early Exit

The standard version keeps making passes even after the list is sorted — pure wasted work. The fix is one simple idea: if a full pass makes no swaps, the list is already sorted, so stop. Cambridge calls this the efficient bubble sort.

Exam tip:

9618/22 O/N 2022 Q asked candidates to "Write an efficient bubble sort algorithm" for 8 marks.
The word "efficient" in the question is the trigger: the mark scheme reserves marks specifically for the Boolean flag, resetting it each pass, and the loop that terminates when no swaps occur.
Writing the basic version caps your marks.

def bubble_sort_optimised(numbers):
    n = len(numbers)
    swapped = True  # forces the loop to run at least once
    while swapped == True:
        swapped = False  # reset at the START of every pass
        for i in range(n - 1):
            if numbers[i] > numbers[i + 1]:
                temp = numbers[i]
                numbers[i] = numbers[i + 1]
                numbers[i + 1] = temp
                swapped = True  # a swap happened this pass
    return numbers

Key rule — reset swapped each pass:

swapped must start as True (so the while loop is entered) and must be reset to False at the start of every pass, not just once before the loop.
Forgetting the reset makes the loop run forever, because swapped can never return to False.

Your Turn — How many passes on [2, 1, 3, 4, 5]?

State how many passes the optimised bubble sort performs on the list [2, 1, 3, 4, 5], and explain why.

Hint:

Pass 1: swap (2,1), then no more swaps
Pass 2: no swaps at all
Pass 2 makes no swaps, so the loop ends

Your Turn — Passes on sorted and unsorted lists

(a) How many passes does the optimised bubble sort perform on an already-sorted list? (b) How many passes on [6, 1, 4, 2]? Explain each.

Hint:

(a) Already sorted: 1 pass, no swaps, loop ends
(b) From the trace in 14.3: pass 3 had no swaps

Exam tip:

If the question gives you pseudocode or a code skeleton, follow its structure exactly — do not "improve" it with a flag the question never asked for.
Use the optimised version only when the question asks for an efficient bubble sort or leaves the design to you.
Also watch for while swapped = True (assignment) instead of while swapped == True (comparison) — a classic syntax error.

Knowledge Check 3

Tracing & Optimised Version

Knowledge Check 5

Swap Mechanics & Common Errors

14.5 Performance of Bubble Sort

Scenario	Passes	Comparisons	Big O
Best case (already sorted, optimised)	1	n - 1	O(n)
Worst case (reverse sorted)	n - 1	~(n-1)²	O(n²)
Average case	~n/2	~n²/2	O(n²)

Key rule:

The performance of bubble sort depends on both the initial order of the data and the number of items.
Already-sorted data finishes in 1 pass; reverse-sorted data needs maximum passes.
Doubling the list roughly quadruples the work (O(n²)).

Exam tip:

For a 2-mark "explain why performance depends on the initial order" question, name both ends: already-sorted data needs only one pass before the early exit stops the sort, while reverse-ordered data forces the maximum number of passes with a swap at every comparison.
One mark per end.

Knowledge Check 4

Performance

14.6 Full Exam-Style Question

Nazifa is writing a program for her school's sports day. The finishing times for one race, in seconds, are stored in a list:

Times = [14.2, 12.8, 15.1, 11.9, 13.5, 12.1, 14.8, 13.0]

(a) — Describe in prose [4 marks] Describe how a bubble sort arranges the values in Times into ascending order. Do not use code or pseudocode statements.

Your Turn — (a) Model answer

Describe how a bubble sort arranges the values into ascending order. Do not use code. [4 marks]

Hint:

Compare adjacent/neighbouring values
Swap if left is greater than right
Repeat passes through the list
Largest value moves to end each pass
Stop when a pass makes no swaps

(b) — Efficient bubble sort [6 marks] Write a Python function BubbleSort(Times) that uses an efficient bubble sort to arrange the contents of Times into ascending order and returns the sorted list. Your function should stop as soon as the list is sorted.

Your Turn — (b) Model answer

Write an efficient bubble sort function BubbleSort(Times) that stops when sorted. [6 marks]

Hint:

Use a Boolean flag (swapped)
while swapped == True: loop
Reset swapped = False at start of each pass
Set swapped = True when a swap occurs
Three-line swap with temp
Return the sorted list

(c) — Explain performance [2 marks] Nazifa notices her function finishes much faster when the times are entered in nearly the correct order. Explain why.

Your Turn — (c) Model answer

Explain why the efficient bubble sort finishes faster when data is nearly sorted. [2 marks]

Hint:

Nearly-sorted data needs fewer swaps
A pass with no swaps ends the loop early

Knowledge Check 6

Key Points Recap

✓ Key Points Summary

Bubble sort compares adjacent neighbours and swaps them if in the wrong order.

After pass k, the largest k values are in their final positions at the end.

The list is sorted when a complete pass makes no swaps.

Standard version: two nested for loops, both range(n-1).

Three-line swap: temp = a; a = b; b = temp — save, overwrite, restore.

Inner loop is range(n-1), never range(n) — comparison reaches i+1.

For descending order: change > to < in the comparison.

String comparison with > works alphabetically in Python.

Optimised version: Boolean flag (swapped), while loop, early exit.

swapped must start True (enter loop) and reset to False each pass.

Forgetting to reset swapped causes an infinite loop.

In a trace table, show EVERY comparison including "no swap" rows.

Big O: O(n²) worst case, O(n) best case (optimised, already sorted).

Performance depends on initial order AND number of items.

Use the optimised version only when the question says "efficient".

while swapped = True is a syntax error — use == for comparison.

14.7 Practice Tasks

Fifteen exam-style bubble sort tasks. Each shows only the question — click Hint for the thought process, or Help for the worked solution.

Exam tip:

For every bubble sort task, the marker checks: (1) correct nested loops (both range(n-1)), (2) correct comparison (numbers[i] > numbers[i+1]), (3) complete three-line swap with temp, (4) for optimised: Boolean flag + while loop + reset each pass.
The most common mark loss is using range(n) instead of range(n-1).

1Practice Task — Standard bubble sort [4 marks]

Write a Python function bubble_sort(numbers) that sorts a list in ascending order using the standard bubble sort and returns the sorted list.

2Practice Task — Efficient bubble sort [6 marks]

Write an efficient bubble sort function that stops as soon as the list is sorted. Use a Boolean flag.

3Practice Task — Descending order [4 marks]

Write a function bubble_sort_desc(numbers) that sorts in DESCENDING order (largest first).

4Practice Task — Sort names [4 marks]

Write a bubble sort that arranges ["Nawal", "Aymaan", "Mohar"] in alphabetical order.

5Practice Task — Count swaps [4 marks]

Write a function that sorts [9, 4, 7, 1] and prints the total number of swaps made.

6Practice Task — Trace [5, 3, 8, 2] [6 marks]

Trace bubble sort (ascending) on [5, 3, 8, 2]. Show every comparison in every pass.

7Practice Task — Describe in prose [4 marks]

Describe how a bubble sort arranges data into ascending order. Do not use code or pseudocode.

8Practice Task — Why three-line swap? [2 marks]

Explain why a temporary variable is needed when swapping two list elements.

9Practice Task — Why range(n-1)? [2 marks]

Explain why the inner loop uses range(n-1) instead of range(n).

10Practice Task — Big O [2 marks]

What is the Big O of bubble sort (worst case), and why?

11Practice Task — Best case [2 marks]

What is the best case for the OPTIMISED bubble sort, and what is its Big O?

12Practice Task — Missing reset [2 marks]

What happens if you forget to reset swapped = False at the start of each pass?

13Practice Task — Performance depends on order [2 marks]

Explain why the performance of bubble sort depends on the initial order of the data.

14Practice Task — while swapped = True error [2 marks]

A student writes while swapped = True instead of while swapped == True. Explain the error.

15Practice Task — Full exam question [12 marks]

Times = [14.2, 12.8, 15.1, 11.9, 13.5, 12.1, 14.8, 13.0]. (a) Describe bubble sort in prose [4]. (b) Write efficient BubbleSort(Times) [6]. (c) Explain why it is faster on nearly-sorted data [2].

Question Bank

Answer all questions, then press Submit Quiz to see your score.

0/12 answered

Question 1Multiple Choice

What does bubble sort do in each pass?

Question 2True / False

After pass k, the largest k values are in their final positions.

Question 3Multiple Choice

Why use range(n-1) for the inner loop?

Question 4Multiple Choice

Why does the swap use a temp variable?

Question 5True / False

The optimised version stops when a pass makes no swaps.

Question 6Multiple Choice

What is the Big O of bubble sort (worst case)?

Question 7Multiple Choice

What is the best case for the OPTIMISED bubble sort?

Question 8True / False

To sort descending, change > to < in the comparison.

Question 9Multiple Choice

What happens if swapped is not reset to False each pass?

Question 10Multiple Choice

In a trace table, what must you show?

Question 11True / False

while swapped = True is correct Python.

Question 12Multiple Choice

The standard version always does how many passes?

Answer all 12 questions to enable submission.