A First Taste of Algorithms · Lab 7: The Honest Die

3. The adversary’s kill, then the coins’ rescue

Quicksort with the predictable rule — first item as pivot — and a comparison counter riding along:

def quicksort_first(items):
    if len(items) <= 1:
        return [items, 0]
    pivot = items[0]
    smaller = []
    bigger = []
    for x in items[1:]:               # items[1:]: everything after the pivot
        if x < pivot:
            smaller.append(x)
        else:
            bigger.append(x)
    left = quicksort_first(smaller)
    right = quicksort_first(bigger)
    return [left[0] + [pivot] + right[0], left[1] + right[1] + len(items) - 1]

shuffled = list(range(200))
random.shuffle(shuffled)
print("shuffled input:", quicksort_first(shuffled)[1], "comparisons")

On shuffled input: respectable, n log n-ish. Now be the adversary — you know the rule, so supply the killer:

print("sorted input:", quicksort_first(list(range(200)))[1], "comparisons")

Quadratic: 19,900 = 200·199/2, the full bill, on the most innocent input there is. Then push the adversary’s advantage to its conclusion: try list(range(5000)) and read the error to its last line — Lab 3’s old enemy, because the lopsided recursion is n deep. The adversary didn’t just slow your algorithm; it crashed it, with sorted data.

The rescue is one line — the pivot by coin:

def quicksort_random(items):
    if len(items) <= 1:
        return [items, 0]
    pivot = random.choice(items)
    smaller = []
    bigger = []
    for x in items:
        if x < pivot:
            smaller.append(x)
        elif x > pivot:
            bigger.append(x)          # equal-to-pivot items sit out: they're placed
    left = quicksort_random(smaller)
    right = quicksort_random(bigger)
    return [left[0] + [pivot] + right[0], left[1] + right[1] + len(items) - 1]

print(quicksort_random(list(range(5000)))[1], "comparisons on the killer input")

The input that crashed the predictable version is now unremarkable. Run that cell five times: five different comparison counts, all in the same healthy neighborhood. The cost has become a random quantity — which is exactly why the next section needs a new instrument.

4. The distribution, drawn

A random cost is not one number; it is a shape, and the instrument for shapes is the histogram: chop the number line into bins, count how many runs land in each, draw the counts as bars. One new plotting move, plt.hist:

import matplotlib.pyplot as plt

n = 256
counts = []
for _ in range(2000):
    counts.append(quicksort_random(list(range(n)))[1])

mean = sum(counts) / len(counts)
print("mean:", round(mean, 1), "   smallest:", min(counts), "   largest:", max(counts))

plt.hist(counts, bins=40)
plt.xlabel("comparisons (n = 256)")
plt.ylabel("how many of the 2000 runs")
plt.show()

Read your hill. The mean sits near 2,125 — the deep water’s exact 2(n+1)Hₙ − 4n, not the asymptotic slogan 2n ln n ≈ 2,839; check both against your printout and note which one your data votes for. Then the question the picture answers and the mean cannot: where is the worst case? It is n(n−1)/2 = 32,640 — find the largest of your 2,000 runs and see how breathtakingly far short of the cliff even your unluckiest run fell. Two thousand genuine gambles, and the catastrophe wasn’t merely avoided; it was never in the room. That concentration — not the average alone — is what the chapter meant by trusting the gamble.

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