A First Taste of Algorithms

Lab 6: Counted and Clocked

✦ ✦ ✦

Accompanies Chapter 6. Until now this book has counted and refused to clock. Today both instruments run side by side: the count predicts the shapes, the clock reveals the constants, and a plot — your first — shows the two sorts diverging exactly as the chapter promised. Two instruments arrive, each with its debt: the clock because constants are real, the plot because six chapters of tables have earned a picture.

1. The plodder, counted

Insertion sort, exactly as hands do it — each arrival walks left past everything bigger:

def insertion_sort_count(a):
    comparisons = 0
    for i in range(1, len(a)):
        arriving = a[i]
        j = i - 1
        while j >= 0 and a[j] > arriving:
            comparisons = comparisons + 1
            a[j + 1] = a[j]          # shift the bigger card right
            j = j - 1
        if j >= 0:
            comparisons = comparisons + 1   # the comparison that said "stop"
        a[j + 1] = arriving
    return comparisons

hand = [7, 3, 9, 1, 8]
print(insertion_sort_count(hand), hand)

One behavior to notice and remember: this sorter works in place — it rearranges the very list you hand it, the way your hands rearrange the actual cards (print hand after the call: it changed). Merge sort, by contrast, built a new sorted list and left its input alone. The difference seems cosmetic today; in §3 it becomes load-bearing. Check the count against your paper run from Fluency 1.1. Then the gait audit, worst case (reverse-sorted), in the house style:

for n in [8, 32, 128, 512, 2048]:
    print(n, insertion_sort_count(list(range(n, 0, -1))))

Verify each row equals n(n − 1)/2 exactly, and read the gait: n quadruples each row — the count multiplies by sixteen. The n² signature, measured.

2. The race, counted

Retype merge sort and its step counter from Lab 3 (merge, merge_sort_count) — retyping is review — then race the two on the same worst-case inputs:

for n in [8, 32, 128, 512, 2048]:
    ins = insertion_sort_count(list(range(n, 0, -1)))     # fresh worst case each —
    mrg = merge_sort_count(list(range(n, 0, -1)))[1]      # remember: insertion mutates
    print(n, "  insertion:", ins, "  merge:", mrg, "  ratio:", round(ins / mrg, 1))

Read the ratio column: about 1 at the top, about 90 at the bottom, roughly doubling with each doubling of n. In the counted currency the halver wins at every size on this table — even n = 8 — and the gap only opens. Hold that fact; the clock is about to complicate it.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses