def show_step(cards: list, compared: tuple = None, label: str = ""):
"""Print the list, highlighting the compared positions."""
parts = []
for idx, val in enumerate(cards):
if compared and idx in compared:
parts.append(f"[{val}]")
else:
parts.append(f" {val} ")
line = " ".join(parts)
if label:
print(f"{label:>12s}: {line}")
else:
print(f" {line}")18 Sorting Algorithms
18.1 The Sorting Problem
Input: A sequence of n comparable elements (e.g. numbers, strings).
Output: The same elements rearranged in non-descending order.
Example: - Input: [4, 2, 5, 1, 3] - Output: [1, 2, 3, 4, 5]
Sorting is one of the most fundamental operations in computer science. There are many different algorithms that solve this problem — you just invented one (or more!) with your playing cards.
18.2 Pseudocode Conventions (Quick Reference)
Recall from last week:
| Element | Python | Pseudocode |
|---|---|---|
| Assignment | x = 5 |
x ← 5 |
| Condition | if x > 0: |
IF x > 0 THEN |
| Else | else: |
ELSE |
| End block | (indentation) | END IF |
| While loop | while x > 0: |
WHILE x > 0 DO |
| For loop | for i in range(n): |
FOR i ← 0 TO n-1 DO |
| End for | (indentation) | END FOR |
| Function | def f(a, b): |
FUNCTION f(a, b) |
| Return | return a |
RETURN a |
New for today — SWAP:
| Python | Pseudocode |
|---|---|
a, b = b, a |
SWAP a AND b |
cards[i], cards[j] = cards[j], cards[i] |
SWAP cards[i] AND cards[j] |
Python lets you swap two variables in one line: a, b = b, a. This works because Python evaluates the right side first, then assigns both values simultaneously.
18.3 Helper: Visualising Each Step
The function below prints the current state of the list and highlights which positions were just compared. Use it inside your sorting function to trace what is happening.
18.4 Your Sorting Algorithm
You invented a sorting strategy with the playing cards. Now implement it in Python!
Task:
- If you haven’t already, write pseudocode for your strategy on the worksheet.
- Translate your pseudocode into the Python function below.
- Use
show_step()to visualise what your algorithm does. - Test it — does it produce a sorted list for every input?
Don’t worry about efficiency or elegance yet. The goal is to get a working implementation of your strategy.
18.5 Named Sorting Algorithms
Now that you have a working sorting function, let’s look at two well-known sorting algorithms. You may recognise your own strategy in one of them — or discover a completely different approach.
18.6 Selection Sort
Core idea: Repeatedly find the minimum of the unsorted portion and swap it into the next position.
18.6.1 Pseudocode
FUNCTION selection_sort(cards, n)
FOR i ← 0 TO n - 2 DO
min_pos ← i
FOR j ← i + 1 TO n - 1 DO
IF cards[j] < cards[min_pos] THEN
min_pos ← j
END IF
END FOR
SWAP cards[i] AND cards[min_pos]
END FOR
END FUNCTION18.6.2 Walkthrough (5 cards: 4, 2, 5, 1, 3)
| Pass | Unsorted portion | Minimum | Swap with pos | Result |
|---|---|---|---|---|
| 1 | 4, 2, 5, 1, 3 | 1 (pos 3) | pos 0 | 1, 2, 5, 4, 3 |
| 2 | 2, 5, 4, 3 | 2 (pos 1) | pos 1 (no move) | 1, 2, 5, 4, 3 |
| 3 | 5, 4, 3 | 3 (pos 4) | pos 2 | 1, 2, 3, 4, 5 |
| 4 | 4, 5 | 4 (pos 3) | pos 3 (no move) | 1, 2, 3, 4, 5 |
18.6.3 Exercise: Implement Selection Sort
Translate the pseudocode above into Python. Use show_step() to print the state after each pass.
Click to reveal the solution
18.7 Bubble Sort
Core idea: Walk through the list from left to right, compare adjacent elements, and swap them if they are in the wrong order. Repeat until the list is sorted. The largest unsorted element “bubbles up” to the end in each pass.
18.7.1 Pseudocode
FUNCTION bubble_sort(cards, n)
FOR i ← 0 TO n - 2 DO
FOR j ← 0 TO n - 2 - i DO
IF cards[j] > cards[j + 1] THEN
SWAP cards[j] AND cards[j + 1]
END IF
END FOR
END FOR
END FUNCTION18.7.2 Walkthrough (5 cards: 4, 2, 5, 1, 3)
Pass 1: (compare positions 0–1, 1–2, 2–3, 3–4)
| Compare | Before | Swap? | After |
|---|---|---|---|
| pos 0 & 1 | 4 2 5 1 3 | Yes | 2 4 5 1 3 |
| pos 1 & 2 | 2 4 5 1 3 | No | 2 4 5 1 3 |
| pos 2 & 3 | 2 4 5 1 3 | Yes | 2 4 1 5 3 |
| pos 3 & 4 | 2 4 1 5 3 | Yes | 2 4 1 3 5 |
→ After pass 1: 2, 4, 1, 3, 5 — the 5 has bubbled to the end.
Passes 2–3 continue until the list is fully sorted: 1, 2, 3, 4, 5.
18.7.3 Exercise: Implement Bubble Sort
Translate the pseudocode above into Python. Use show_step() to print the state after each pass.
Click to reveal the solution
18.8 Testing Your Implementations
Run the cell below to test whichever sorting function you implemented. Then test selection_sort and bubble_sort after you’ve implemented them.
import random
def test_sort(sort_func, uses_bounds=False):
"""Test a sorting function on several inputs."""
test_cases = [
[4, 2, 5, 1, 3],
[1, 2, 3, 4, 5], # already sorted
[5, 4, 3, 2, 1], # reverse sorted
[1], # single element
[3, 3, 1, 2, 2], # duplicates
random.sample(range(1, 11), 10), # random 10 elements
]
all_passed = True
for i, case in enumerate(test_cases):
original = case.copy()
expected = sorted(case)
if uses_bounds:
sort_func(case, 0, len(case) - 1)
else:
sort_func(case)
if case == expected:
print(f"Test {i+1}: PASS {original} → {case}")
else:
print(f"Test {i+1}: FAIL {original} → {case} (expected {expected})")
all_passed = False
if all_passed:
print("\n✓ All tests passed!")
else:
print("\n✗ Some tests failed — check your code.")18.9 Counting Comparisons
How many comparisons does each algorithm need? The functions below are instrumented versions that count every comparison. Run them on the same input to compare.
def selection_sort_count(cards: list) -> int:
"""Selection Sort that returns the number of comparisons."""
n = len(cards)
comparisons = 0
for i in range(n - 1):
min_pos = i
for j in range(i + 1, n):
comparisons += 1
if cards[j] < cards[min_pos]:
min_pos = j
cards[i], cards[min_pos] = cards[min_pos], cards[i]
return comparisons
def bubble_sort_count(cards: list) -> int:
"""Bubble Sort that returns the number of comparisons."""
n = len(cards)
comparisons = 0
for i in range(n - 1):
for j in range(n - 1 - i):
comparisons += 1
if cards[j] > cards[j + 1]:
cards[j], cards[j + 1] = cards[j + 1], cards[j]
return comparisons