Sorting — Bubble Sort

By the end of this lesson you can:

• Implement bubble sort with a nested loop.
• Apply two optimisations — outer-bound shrink, early-exit on no swaps.
• Explain why bubble sort is O(n²) — and what that means for big lists.
• Know when not to use it (almost always — but it's great for tiny lists or when a list is almost sorted).

Start:     [5, 3, 8, 1, 4]
                ↕
Pass 1:    [3, 5, 8, 1, 4]   compare (5,3) swap, (5,8) ok, (8,1) swap, (8,4) swap
           [3, 5, 1, 8, 4]
           [3, 5, 1, 4, 8]   8 has "bubbled" to the end

Pass 2:    [3, 1, 5, 4, 8]
           [3, 1, 4, 5, 8]   5 has bubbled to its position

Pass 3:    [1, 3, 4, 5, 8]   3 bubbled left, 4 settled

Pass 4:    [1, 3, 4, 5, 8]   no swaps — DONE

Each pass moves the largest unsorted item to its final position. After N-1 passes, everything is in order.

Naïve version

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]


data = [5, 3, 8, 1, 4]
bubble_sort(data)
print(data)        # [1, 3, 4, 5, 8]

Outer loop runs N times. Inner loop scans N-1 pairs. Swap when out of order. N² comparisons in the worst case.

Optimisation 1 · Shrink the inner loop

After pass i, the last i items are guaranteed sorted. No need to scan them again.

def bubble_sort_v2(lst):
    n = len(lst)
    for i in range(n - 1):
        for j in range(n - 1 - i):       # ← stop earlier each pass
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

Roughly halves the work. Still O(n²) — but with a smaller constant.

Optimisation 2 · Early exit on no swaps

If a pass made no swaps, the list is already sorted. Stop.

def bubble_sort_v3(lst):
    n = len(lst)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                swapped = True
        if not swapped:
            return                        # sorted!

Best case (already sorted) becomes O(n) — one full pass with no swaps, then exit. Worst case (reverse-sorted) is still O(n²).

Pure-function version

If you want sorted output without mutating the input, return a new list:

def bubble_sorted(lst):
    result = list(lst)        # copy
    bubble_sort_v3(result)
    return result

Tracking comparisons and swaps

def bubble_sort_traced(lst):
    n = len(lst)
    comparisons = 0
    swaps = 0
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            comparisons += 1
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return comparisons, swaps

Useful for empirical complexity verification.

When it's actually OK to use bubble sort

• Lists shorter than ~20 items — overhead of cleverer sorts isn't worth it.
• Lists that are already nearly sorted — with the early-exit, it's near-O(n).
• Teaching. (Today.)

For anything bigger, use Python's built-in sorted() — which uses Timsort, an algorithmically optimal hybrid. We'll meet it in PY-L3-41.

Save as bubble_visual.py:

# bubble_visual.py — print each pass to see the bubbling

def bubble_sort_visual(lst):
    n = len(lst)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                swapped = True
        print(f"  Pass {i + 1}: {lst}")
        if not swapped:
            print(f"  (early exit — sorted after pass {i + 1})")
            return


data = [5, 1, 4, 2, 8, 3]
print(f"Start:  {data}")
bubble_sort_visual(data)
print(f"Final:  {data}")

Output

Start:  [5, 1, 4, 2, 8, 3]
  Pass 1: [1, 4, 2, 5, 3, 8]
  Pass 2: [1, 2, 4, 3, 5, 8]
  Pass 3: [1, 2, 3, 4, 5, 8]
  Pass 4: [1, 2, 3, 4, 5, 8]
  (early exit — sorted after pass 4)
Final:  [1, 2, 3, 4, 5, 8]

Read the diff

Each pass shows the "biggest unsorted item" moving to the right. Pass 1: 8 reaches the end. Pass 2: 5 is in place. Pass 3: list is fully sorted. Pass 4 confirms (no swaps) and exits. Six items, four passes — way fewer than the worst-case 30.

Bubble sort: compare neighbours, swap if wrong order, repeat. Two simple optimisations — shrink the inner loop each pass, early-exit when no swaps. O(n²) average and worst case; O(n) when nearly sorted. Memorable, easy to teach, almost never the right choice in production. Tomorrow brings insertion sort — same complexity class but better in practice for nearly-sorted data.