Imagine bubbles rising to the top of a glass — the biggest bubbles reach the top first. Bubble sort works the same way: larger values "bubble up" to the end of the list.

How Bubble Sort Works

Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they're in the wrong order. Each "pass" places the next largest value in its correct position.

Algorithm:

For i from 0 to n-2:          # Number of passes
    For j from 0 to n-2-i:    # Compare adjacent pairs
        If items[j] > items[j+1]:
            Swap items[j] and items[j+1]

Trace example: [64, 34, 25, 12]

Pass 1: [34, 25, 12, 64]  ← 64 bubbled to end
Pass 2: [25, 12, 34, 64]  ← 34 bubbled into place
Pass 3: [12, 25, 34, 64]  ← Sorted!

Practice 1

1. Trace bubble sort on [7, 3, 9, 1]. Show each pass.
2. How many comparisons in one pass for a list of 10 items?

Implementation with Early Exit

def bubble_sort(items):
    n = len(items)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:     # No swaps = already sorted!
            break
    return items

Practice 2

1. Add a counter to track how many swaps bubble sort makes on [5, 1, 4, 2, 8].
2. What's the best-case and worst-case time complexity of bubble sort?

Think about how you sort a hand of playing cards. You pick up one card at a time and insert it into the correct position among the cards you're already holding. That's insertion sort!

How Insertion Sort Works

The algorithm builds the sorted list one element at a time. It takes each element and inserts it into its correct position in the already-sorted portion.

Algorithm:

For i from 1 to n-1:
    key = items[i]         # The element to insert
    j = i - 1              # Start from the previous element
    While j >= 0 AND items[j] > key:
        items[j+1] = items[j]   # Shift right
        j = j - 1
    items[j+1] = key       # Insert key in correct position

Trace: [64, 34, 25, 12]

i=1, key=34: [34, 64, 25, 12]  ← 34 inserted before 64
i=2, key=25: [25, 34, 64, 12]  ← 25 inserted at start
i=3, key=12: [12, 25, 34, 64]  ← 12 inserted at start

Practice 1

1. Trace insertion sort on [5, 2, 9, 1, 5]. Show the list after each insertion.
2. Why does the inner while loop shift elements instead of just swapping?

Bubble Sort vs Insertion Sort

Practice 2

1. Write insertion sort to sort a list of names alphabetically.
2. Which sorting algorithm would you use for a nearly-sorted list of 20 items? Why?