An algorithm has a loop nested inside another loop, and each loop runs up to n times. According to the textbook's classification, its time complexity is:

Proportional to 2n, since there are two loops

Assertion (A): After k passes of bubble sort in ascending order, the last k elements of the list are in their final positions. Reason (R): Each pass of bubble sort carries the largest element of the unsorted part to the end of that part.

Both A and R are true, and R is the correct explanation of A

Both A and R are true, but R is not the correct explanation of A

Sorting

A dictionary is useful because its words are in alphabetical order; the same words in random order would be almost impossible to search. Sorting — arranging elements in ascending or descending order, numerically or alphabetically — is what makes fast searching, ranking and reporting possible. This chapter works through the three sorting algorithms of the syllabus, bubble, selection and insertion sort, showing exactly how the list looks after each pass, and then how their running time grows with the size of the list. The paper sets "the list after the second pass" questions for all three, so practise the passes on paper until they are automatic.

Bubble Sort

Bubble sort repeatedly steps through the list comparing adjacent elements and swapping any pair that is out of order. In one pass, the largest element still in the unsorted part is carried along to the end — it "bubbles up" — so after pass 1 the largest is last, after pass 2 the two largest are in place, and so on. A list of n elements needs n − 1 passes, and pass k (counting from 1) makes n − k comparisons, since the last k − 1 elements are already settled. The total is (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparisons: 10 for five elements.

Pass 1 of bubble sort on [5, 1, 4, 2, 8], ascending
Compare	Action	List after
5 and 1	swap	[1, 5, 4, 2, 8]
5 and 4	swap	[1, 4, 5, 2, 8]
5 and 2	swap	[1, 4, 2, 5, 8]
5 and 8	no swap	[1, 4, 2, 5, 8]

In Python the book's version is two nested loops; changing > to < sorts in descending order instead:
n = len(L)
for i in range(n - 1):
for j in range(n - 1 - i):
if L[j] > L[j + 1]:
L[j], L[j + 1] = L[j + 1], L[j]
A common refinement keeps a flag recording whether a pass made any swap and stops as soon as one makes none — on an already sorted list that stops after a single pass.

Selection Sort

Selection sort treats the list as two parts: a sorted part on the left, initially empty, and an unsorted part on the right. In each pass it selects the smallest element of the unsorted part and swaps it with the leftmost unsorted element, so the sorted part grows by one. After n − 1 passes the list is sorted. Each pass makes at most one swap, so selection sort does at most n − 1 swaps in all — far fewer than bubble sort can — but it still scans the whole unsorted part every time, whatever the input looks like.

Worked example on [29, 10, 14, 37, 13]. Pass 1: the smallest is 10; swap it with 29 → [10, 29, 14, 37, 13]. Pass 2: the smallest of [29, 14, 37, 13] is 13; swap it with 29 → [10, 13, 14, 37, 29]. Pass 3: 14 is already the smallest of what remains, so it swaps with itself. Pass 4: swap 37 and 29 → [10, 13, 14, 29, 37].

Insertion Sort

Insertion sort is how many people sort a hand of cards. The first element on its own is a sorted part. Each later element is taken in turn and inserted into its correct place in the sorted part on its left: elements of the sorted part larger than it are shifted one place right, and it drops into the gap. After the element at index i has been inserted, the first i + 1 elements are in order — but, unlike selection sort, they are not yet in their final positions, because smaller elements may still arrive from the right.

Worked example on [7, 3, 5, 1]. Insert 3: it is smaller than 7, so 7 shifts right → [3, 7, 5, 1]. Insert 5: 7 shifts right, 3 does not → [3, 5, 7, 1]. Insert 1: 7, 5 and 3 all shift → [1, 3, 5, 7]. On a list that is already sorted, each new element is compared once and never moved, so insertion sort finishes in a single sweep of n − 1 comparisons.

🧠 Tell the three apart after one pass

Bubble: the largest has reached the right end. Selection: the smallest has reached the left end, by one swap. Insertion: the first two elements are in order with each other, and nothing to their right has moved.

Time Complexity

Time complexity describes how the number of basic steps an algorithm takes grows as the input size n grows, ignoring the speed of a particular machine. The book uses three simple rules. An algorithm with no loop, doing a fixed amount of work, has constant time complexity. One with a single loop running from 1 to n has linear complexity, proportional to n. One with a loop inside a loop, each running up to n, has quadratic complexity, proportional to n². Bubble, selection and insertion sort are all built from nested loops, so all three are quadratic: doubling the list roughly quadruples the work in the worst case.

Key takeaways

Bubble sort swaps adjacent out-of-order pairs; each pass carries the largest remaining element to the end, and n elements need n − 1 passes.
Without an early exit, bubble sort makes n(n − 1)/2 comparisons — 10 for five elements.
Selection sort picks the smallest unsorted element and swaps it to the front of the unsorted part: at most one swap per pass.
Insertion sort inserts each element into the sorted part on its left, shifting larger ones right; on sorted input it needs only n − 1 comparisons.
No loop means constant time, one loop linear, nested loops quadratic; all three sorts are quadratic, proportional to n².

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The list [5, 1, 4, 2, 8] is sorted in ascending order by bubble sort. What does the list look like after the first pass?
1. [1, 5, 4, 2, 8]
2. [1, 2, 4, 5, 8]
3. [1, 4, 2, 5, 8]
4. [1, 4, 5, 2, 8]
Show answer
Answer: C — [1, 4, 2, 5, 8]
Comparing neighbours: 5 and 1 swap, 5 and 4 swap, 5 and 2 swap, and 5 and 8 stay, so 5 travels to just before 8 and the list is [1, 4, 2, 5, 8]. [1, 5, 4, 2, 8] stops after the first comparison, and [1, 4, 5, 2, 8] after the second. The fully sorted list needs a second pass to move 2 past 4.
Selection sort is applied to [29, 10, 14, 37, 13] to arrange it in ascending order. What is the list after the second pass?
1. [10, 13, 14, 37, 29]
2. [10, 14, 29, 37, 13]
3. [10, 13, 14, 29, 37]
4. [10, 29, 14, 37, 13]
Show answer
Answer: A — [10, 13, 14, 37, 29]
Pass 1 swaps the smallest, 10, with 29: [10, 29, 14, 37, 13]. Pass 2 finds the smallest of the remaining four, 13, and swaps it with 29: [10, 13, 14, 37, 29]. [10, 29, 14, 37, 13] is the state after one pass only. [10, 14, 29, 37, 13] inserts instead of swapping, which is insertion sort, and the fully sorted list needs four passes.
Insertion sort is applied to [7, 3, 5, 1] in ascending order. What is the list after the elements 3 and 5 have each been inserted?
1. [1, 3, 5, 7]
2. [3, 7, 5, 1]
3. [1, 3, 7, 5]
4. [3, 5, 7, 1]
Show answer
Answer: D — [3, 5, 7, 1]
Inserting 3 shifts 7 right: [3, 7, 5, 1]. Inserting 5 shifts 7 right again but not 3: [3, 5, 7, 1]. The 1 has not been reached yet, so it stays at the end. [3, 7, 5, 1] is the list after only one insertion, and [1, 3, 7, 5] moves the smallest element to the front first, which is what selection sort does.
Bubble sort, without any early-exit check, is run on a list of 5 elements. How many comparisons does it make in total?
1. 25
2. 20
3. 10
4. 4
Show answer
Answer: C — 10
There are four passes, and each compares one pair fewer than the last because another element has settled at the end: 4 + 3 + 2 + 1 = 10, which is n(n − 1)/2 with n = 5. 25 is n², the order of growth rather than the exact count. 20 assumes every pass makes four comparisons, and 4 counts the passes instead of the comparisons.
What is the output of the following code?
L = [4, 2, 6, 1]
n = len(L)
for i in range(n - 1):
for j in range(n - 1 - i):
if L[j] < L[j + 1]:
L[j], L[j + 1] = L[j + 1], L[j]
print(L)
1. [1, 2, 4, 6]
2. [6, 4, 2, 1]
3. [4, 6, 2, 1]
4. [2, 4, 1, 6]
Show answer
Answer: B — `[6, 4, 2, 1]`
This is the bubble sort loop with the comparison reversed: a pair is swapped when the left element is smaller, so smaller values sink to the end and the list ends in descending order, [6, 4, 2, 1]. The ascending answer is the trap for anyone who recognises the loop shape without reading the < sign. [4, 6, 2, 1] is the list after the first pass only.
An algorithm has a loop nested inside another loop, and each loop runs up to n times. According to the textbook's classification, its time complexity is:
1. Constant
2. Linear, proportional to n
3. Proportional to 2n, since there are two loops
4. Quadratic, proportional to n²
Show answer
Answer: D — Quadratic, proportional to n²
For each of the n runs of the outer loop the inner loop runs up to n times, so the steps multiply to about n × n — quadratic, the class of all three sorting algorithms here. The 2n option adds the loops instead of multiplying them, which would be right only if they ran one after the other. Linear is a single loop, and constant has no loop at all.
In which of these sorting algorithms does each pass perform at most one swap?
1. Bubble sort
2. Selection sort
3. Insertion sort
4. All three of them equally
Show answer
Answer: B — Selection sort
Selection sort scans the unsorted part to find its smallest element and only then makes a single swap to put it in place, so each pass costs at most one swap. Bubble sort can swap at every comparison in a pass, as the first pass on [5, 1, 4, 2, 8] does three times. Insertion sort shifts several elements to open a gap, so it is not limited to one move either.
Assertion (A): After k passes of bubble sort in ascending order, the last k elements of the list are in their final positions. Reason (R): Each pass of bubble sort carries the largest element of the unsorted part to the end of that part.
1. Both A and R are true, and R is the correct explanation of A
2. Both A and R are true, but R is not the correct explanation of A
3. A is true, but R is false
4. A is false, but R is true
Show answer
Answer: A — Both A and R are true, and R is the correct explanation of A
Because every adjacent swap moves the larger value right, the largest unsorted value is pushed all the way to the end of the unsorted part in each pass; after k passes the k largest values occupy the last k places, and no later pass moves them. R states the mechanism that produces A, so it explains it. Calling A false would confuse bubble sort with insertion sort, whose sorted part is not yet final.