Lesson 2: The invariant

One sentence that makes bubble sort obviously correct, and answers "why n - 1 passes".

~10 minutes. Builds on Lesson 1.

The sentence

After pass k, the last k positions hold their final sorted values.

This is a loop invariant: a claim that is true before the loop starts (k = 0, zero positions fixed, trivially true) and stays true after each pass.[1]

Why it holds

Lesson 1 showed one pass carries the largest value of the region it walks to the end of that region. Pass k + 1 walks only positions 0 to n - 1 - k. The largest value in there lands at position n - 1 - k, which is exactly the next slot to fix. The k already-fixed slots hold values at least as large, so the new slot is correct too.

Why n - 1 passes, not n

Apply the invariant with k = n - 1: the last n - 1 positions are correct. Only position 0 is left, and it holds the one remaining value. A single value is trivially sorted. Pass n would compare nothing.

Teaching tip: learners usually accept "n passes" without thinking. Ask "what does the last pass compare?" and let them discover the inner loop bound is zero.

See the green grow

Green bars are the fixed suffix. Watch it grow by exactly one per pass.

Retrieval practice

Primary source

CLRS Problem 2-2 walks the same invariant formally. Read parts (a) to (c).

Anything unclear? Ask your teaching agent - it wrote this lesson and can go deeper on any point.