Sorting Algorithms: Insertion, Selection and Bubble Sort Compared

Give three simple sorts a list of 40 items that is already in order. Insertion sort makes 39 comparisons. Selection sort makes 780. All three produce the same correct output, but one did twenty times the work, and on a list ten times longer the gap would be a hundred times. Understanding why is more useful than memorising "insertion is O(n^2)", because the same reasoning tells you when a quadratic sort is actually the right tool.

Three sorts, one idea each

Imagine a pharmacy cart of medicine boxes that must be shelved in order of expiry week. Each sort is a different way of working through the cart.

• Insertion sort treats the front of the list as an already-sorted hand. Take the next box and slide it left past every box with a later expiry until it fits.
• Selection sort scans everything not yet placed, finds the earliest expiry, and swaps it into the next slot at the front.
• Bubble sort repeatedly walks the row and swaps neighbours that are out of order, so the latest-expiring box drifts to the end on each pass. Stop when a whole pass makes no swap.

The module below implements all three on a copy of the input and counts every comparison (cmp) and every write that moves an item (mv). It also includes a tiny deterministic pseudo-random generator so the "scrambled" input is the same on every machine. Save it as quadratic_sorts.py.

def insertion_sort(a):
    a = list(a)
    comparisons = moves = 0
    for i in range(1, len(a)):
        item = a[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if a[j] > item:
                a[j + 1] = a[j]          # shift the larger one right
                moves += 1
                j -= 1
            else:
                break
        a[j + 1] = item
    return a, comparisons, moves


def selection_sort(a):
    a = list(a)
    comparisons = moves = 0
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            comparisons += 1
            if a[j] < a[smallest]:
                smallest = j
        if smallest != i:
            a[i], a[smallest] = a[smallest], a[i]
            moves += 1
    return a, comparisons, moves


def bubble_sort(a):
    a = list(a)
    comparisons = moves = 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for j in range(end):
            comparisons += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                moves += 1
                swapped = True
        if not swapped:                  # a clean pass means already sorted
            break
    return a, comparisons, moves


def scrambled(n, seed=7):
    """Deterministic pseudo-random list without importing random."""
    out, x = [], seed
    for _ in range(n):
        x = (x * 1103515245 + 12345) % 2**31
        out.append(x % 1000)
    return out


if __name__ == "__main__":
    n = 40
    inputs = {
        "already sorted": list(range(n)),
        "reversed": list(range(n, 0, -1)),
        "scrambled": scrambled(n),
    }
    print(f"{'input (n=40)':16}{'insertion':>16}{'selection':>16}{'bubble':>16}")
    for label, data in inputs.items():
        row = []
        for sort in (insertion_sort, selection_sort, bubble_sort):
            result, comps, moves = sort(data)
            assert result == sorted(data)
            row.append(f"{comps:4d} cmp {moves:4d} mv")
        print(f"{label:16}" + "".join(f"{cell:>16}" for cell in row))

input (n=40)           insertion       selection          bubble
already sorted    39 cmp    0 mv 780 cmp    0 mv  39 cmp    0 mv
reversed         780 cmp  780 mv 780 cmp   20 mv 780 cmp  780 mv
scrambled        408 cmp  372 mv 780 cmp   37 mv 777 cmp  372 mv

Reading the table

• Selection sort always makes 780 comparisons, whatever the input. Finding the minimum of what remains means looking at all of it: 39 + 38 + ... + 1 = 780, which is n(n-1)/2 for n = 40. It cannot take advantage of order. What it does well is write rarely: at most one swap per position (20 on the reversed list), which matters when each write is expensive, such as flash memory.
• Insertion sort adapts. On sorted input each item takes a single comparison to confirm it is in place (39 total, zero moves). On reversed input every item slides past all earlier ones: 780 comparisons and 780 moves. On scrambled data it lands at about half the worst case, 408.
• Bubble sort with the early exit matches insertion sort's 39 comparisons on sorted input, but its swaps (372 on the scrambled list) are as numerous as insertion's shifts, and it performs far more comparisons on typical data (777). Without the swapped flag it would make 780 comparisons even on sorted input.

Notice that insertion sort and bubble sort both report exactly 372 moves on the scrambled list. That is not a coincidence. An inversion is a pair of items that are in the wrong order relative to each other, and each shift or adjacent swap in these two algorithms removes exactly one inversion. So the number of moves equals the number of inversions in the input: zero for sorted data, n(n-1)/2 for reversed data.

Why the cost is quadratic

The counting argument is the same in all three. Placing each of n items requires looking at a number of other items that grows with n, and doing that n times gives roughly n x n / 2 steps. Double n and the work quadruples. The second snippet checks it by feeding the same generator longer lists.

from quadratic_sorts import insertion_sort, selection_sort, bubble_sort, scrambled

print(f"{'n':>5}{'insertion':>12}{'selection':>12}{'bubble':>12}")
for n in (100, 200, 400, 800):
    data = scrambled(n)
    counts = [sort(data)[1] for sort in (insertion_sort, selection_sort, bubble_sort)]
    print(f"{n:5d}" + "".join(f"{c:12d}" for c in counts))

    n   insertion   selection      bubble
  100        2614        4950        4914
  200       10221       19900       19795
  400       41337       79800       79680
  800      162001      319600      319135

Each doubling of n multiplies the comparisons by almost exactly four. At n = 800 that is already over 300,000 comparisons for selection and bubble sort, and the trend continues: 8,000 items would need roughly a hundred times more. That growth, not the constant factor, is why these sorts are not used on large data.

Common mistakes

• Leaving out bubble sort's early exit. Symptom: an already-sorted list still costs n(n-1)/2 comparisons, and a test that expects linear behaviour on sorted input fails.
• Looping one step too far with `a[j + 1]`. Symptom: IndexError: list index out of range on the last pass. The inner range must stop at end, not len(a).
• Sorting the caller's list by accident. Symptom: data elsewhere in the program changes order. The implementations above start with a = list(a); do the same, or document that the sort is in place.
• Using `>=` instead of `>` in insertion sort. Symptom: items with equal keys come out in reversed order, because equal items now get moved past each other. The sort still looks correct on plain numbers and only shows up with records.
• Testing only on random input. Symptom: bugs and performance problems at the extremes go unnoticed. Always include sorted, reversed, all-equal, empty and one-item inputs.

How this shows up in real projects and interviews

You will almost never ship a hand-written bubble or selection sort; in Python the answer is sorted(). These algorithms matter because interviewers use them to check that you can reason about loops, state complexity with a justification, and say which one behaves best on nearly sorted input (insertion sort). A good answer to "why is it O(n^2)?" uses the counting argument above rather than quoting the table, and mentions inversions if you want to stand out. The honest follow-up, "so why does anyone study these?", has a real answer: insertion sort is the base case inside faster hybrid sorts, and the next lesson, merge sort and quicksort, shows how to get below quadratic.