Lesson 3: Full algorithm and early exit

Assemble the passes, then add the one flag that gives an O(n) best case.

~12 minutes. Builds on Lesson 2.

Naive version

Two loops. The outer counts passes, the inner walks a shrinking region (the invariant from Lesson 2 says the last pass slots are done).

function bubbleSortNaive(a: number[]): number[] {
  const n = a.length;
  for (let pass = 0; pass < n - 1; pass++) {
    for (let j = 0; j < n - 1 - pass; j++) {
      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
    }
  }
  return a;
}

The early-exit flag

If a whole pass makes zero swaps, every neighbour pair is in order, so the array is sorted and remaining passes are wasted. Track it with one boolean.^[1]

function bubbleSort(a: number[]): number[] {
  const n = a.length;
  for (let pass = 0; pass < n - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return a;
}

On an already sorted input this does one pass of n - 1 comparisons and stops: O(n) best case. Without the flag, best case is still O(n²).

Watch the early exit

Nearly sorted input. Count the passes before it stops.

Write it from memory

Close this page. Type bubbleSort in a scratch file. Then run this check in the browser console or with npx tsx:

const cases = [[], [1], [2,1], [5,1,4,2,8], [1,2,3], [3,3,1]];
for (const c of cases) {
  const got = bubbleSort(c.slice());
  const want = c.slice().sort((x, y) => x - y);
  console.log(JSON.stringify(got) === JSON.stringify(want) ? 'ok' : 'FAIL', c);
}

Retrieval practice

Primary source

Wikipedia: Optimizing bubble sort, including the further refinement that remembers the last swap position.

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