Lesson 1: One pass, by hand

The single idea learners must own before anything else: a pass carries the largest element to the end.

~10 minutes. Mission: explain bubble sort to students with visuals.

The idea

Bubble sort walks left to right, comparing each pair of neighbours. If the left one is bigger, swap. That is the whole rule. One full walk is a pass.^[1]

The payoff of one pass: whatever the largest value is, it gets picked up and carried all the way to the last slot. That single fact is the seed of the correctness argument you will teach in Lesson 2.^[2]

Watch one pass

Press Next comparison and say out loud, before pressing, whether it will swap.

Teaching tip: learners most often believe the walk restarts at index 0 after a swap. It does not; it moves on to the next pair.^[3] Make them narrate the index to catch this.

The code for one pass

function onePass(a: number[]): boolean {
  let swapped = false;
  for (let j = 0; j < a.length - 1; j++) {
    if (a[j] > a[j + 1]) {
      [a[j], a[j + 1]] = [a[j + 1], a[j]];
      swapped = true;
    }
  }
  return swapped;
}

Retrieval practice

Do these from memory. No scrolling up.

Your win: you can now show a class one pass on five numbers and predict every swap before it happens. Try it on paper with [3, 9, 2, 7, 1] and check with the visualizer by editing data-values.

Primary source

Read the "Analysis" and "Optimizing bubble sort" sections of Wikipedia: Bubble sort, then step through VisuAlgo once at slow speed.

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

Reference sheetNext: the invariant