Sorting

Putting items in order

• Sorting arranges a list into order, usually smallest first.
• The key move is a swap: exchange two items.
• In Python: a[i], a[j] = a[j], a[i] swaps two list items in one line.

Bubble sort

• Compare each pair of neighbours; swap them if they are out of order.
• After one full pass, the largest item has "bubbled" to the end.
• Repeat the passes until no swaps are needed.

data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if data[j] > data[j + 1]:
            data[j], data[j + 1] = data[j + 1], data[j]
print(data)

Insertion sort

• Treat the left part of the list as already sorted.
• Take the next item and slide it left until it sits in the right place.
• Like sorting playing cards in your hand, one at a time.

data = [3, 1, 2]
for i in range(1, len(data)):
    key = data[i]
    j = i - 1
    while j >= 0 and data[j] > key:
        data[j + 1] = data[j]
        j = j - 1
    data[j + 1] = key
print(data)

Compare them

• Both check roughly n × n pairs, so both are slow on big lists.
• Insertion sort is fast when the list is almost sorted already.
• Faster methods exist, but bubble and insertion are easy to understand.

In Cambridge pseudocode

• Bubble sort with a temp variable for the swap.

FOR i ← 0 TO LENGTH(list) - 2
    FOR j ← 0 TO LENGTH(list) - 2 - i
        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

• Bubble and insertion sort are both O(n²).
• Trace a small list by hand to check your sort works.

Now you try

• Each task changes the list in place — no need to return it.
• Press Check answer to test your code.