The steps of an algorithm.

Step 1 of 6

Exact steps

An algorithm is a finite list of exact steps that solves a problem: each step is so clear it can be carried out without thinking, and the steps always end with the right answer. A recipe is nearly an algorithm; long division is one entirely. A computer can do nothing else: every program is an algorithm written in a language it understands.

The problem here is sorting: putting a row of blocks in order from shortest to tallest. Algorithm is set to Bubble, and its rule is short:

1. Compare two neighbours.
2. If the left one is taller, swap them.
3. Move on to the next pair, to the end of the row. That is one pass.
4. Repeat passes until a whole pass goes by without a single swap.

Watch the blocks: a blue bracket marks a comparison of a pair already in order, and an orange one marks a swap. The plaque under the shelf counts the comparisons and the swaps.

Step 2 of 6

One pass

To compare algorithms without a stopwatch, count their basic steps. In sorting, the basic step is a comparison of two blocks: how many comparisons the algorithm makes before the row is sorted.

Step 3 of 6

The tallest drifts to the end

The name “bubble sort” comes from what happens on every pass: the tallest block floats to the right, like a bubble rising through water. Watch the first pass and think about what it guarantees.

Step 4 of 6

Every pair

Starting order is set to Reversed: the blocks run from tallest to shortest, and every pass will have to swap. Each pass is one shorter than the last, because the block that floated to the end is already in place.

The sum $1 + 2 + \cdots + (n-1)$⁠ is the number of pairs that can be made from $n$⁠ blocks:

$1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$$1 + 2 + \cdots + (n-1) =$$\frac{n(n-1)}{2}$⁠

Step 5 of 6

Counting swaps

A comparison is only half the work; some comparisons end in a swap. Call two blocks with the taller one on the left an inverted pair. Swapping two neighbours fixes exactly their pair, and changes no other pair.

Step 6 of 6

Stopping early

Bubble sort does not keep working for nothing: after a whole pass without a single swap the row is sorted, and it stops. So how much it works depends not only on List size but also on the row it starts from.