Bubble sort

Sorting puts items in order

• Sorting rearranges a list into order — smallest to largest, say.
• Bubble sort is the standard method named in the syllabus.
• It compares neighbours and swaps any that are the wrong way round.

Swapping two values

• To sort, you must swap two items.
• Python can swap in one line: a, b = b, a.

a = 5
b = 9
a, b = b, a
print(a, b)          # 9 5

Bubble sort: compare neighbours

• Walk the list comparing each pair of neighbours.
• If the left one is bigger, swap them — the biggest "bubbles" to the end.
• Repeat the passes until the list is in order.

nums = [5, 1, 4, 2]
for i in range(len(nums) - 1):
    for j in range(len(nums) - 1 - i):
        if nums[j] > nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums)          # [1, 2, 4, 5]

In the exam: bubble sort

• The exam writes bubble sort in pseudocode with nested loops and a swap.

FOR i ← 1 TO N - 1
    FOR j ← 1 TO N - 1
        IF List[j] > List[j + 1] THEN
            Temp ← List[j]
            List[j] ← List[j + 1]
            List[j + 1] ← Temp
        ENDIF
    NEXT j
NEXT i

Common mistakes

• Each pass moves the largest remaining value to the end.
• If a whole pass makes no swaps, the list is already sorted.

Now you try

• Swap two values, then sort a whole list.
• Press Check answer to test your code.