Bubble, Selection and Insertion Sort

All three of these are O(n²) and all three are taught together, which gives the impression they are the same algorithm with cosmetic differences. They are not. They differ in how many writes they do, whether they notice sorted input, and whether they are stable, and those differences decide which one survives into real code.

Bubble sort

Walk the array comparing neighbors and swapping any that are out of order, and after one pass the largest value has been carried to the end. Repeat.

Its one redeeming feature is the early exit: if a whole pass makes no swaps, the array is sorted and you can stop. That makes it O(n) on already-sorted input. Without that check it is O(n²) unconditionally, and the version without the check is the one most people write.

Switch the input to "already sorted" and watch it stop after a single pass with zero writes.

Selection sort

Find the smallest remaining value, swap it into place, repeat. The comparison count is fixed at n(n-1)/2 no matter what, because it always scans the whole remaining array.

What it does have is the fewest writes of any of these: exactly n-1 swaps, regardless of the input. If comparisons are cheap and writes are expensive, which is the case for flash memory or for records that are large to move, that is a real advantage.

It is not stable, and the reason is worth seeing: swapping a distant minimum into position can jump one of a pair of equal values over the other.

Insertion sort

Grow a sorted prefix. Take the next value, slide it left past everything larger, and drop it in. This is how most people sort a hand of cards.

Notice the holding row underneath. While the shifting loop runs, the value being placed is out of the array entirely, held in a variable, and its old slot has been overwritten. That is why the bars briefly show a duplicate: it is real, not a rendering artifact.

Insertion sort is stable, adaptive, and in place. On nearly-sorted input each value moves only a step or two, so the inner loop barely runs and the whole thing is close to O(n). That combination is why it is the only one of the three that appears in production sorts.

Side by side

Run all three on the same input using the full visualizer, and read the table at the bottom. The interesting comparisons are on the non-random presets.

In code

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let i = 0; i < a.length - 1 - pass; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;      // the whole point: sorted input costs one pass
  }
  return a;
}

function selectionSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];   // exactly one swap per i
  }
  return a;
}

function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const value = a[i];        // held out of the array while we shift
    let j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = value;
  }
  return a;
}

Check yourself

As flowcharts

The same algorithms, drawn as flowcharts, where the dashed copper arrows are loops back to an earlier step, and clicking any box with a dot shows why that step is there.

Bubble sort as a flowchart.

Selection sort as a flowchart.

Insertion sort as a flowchart.