Sorting 1: bubble, selection and insertion sort

Selection sort makes exactly 45 comparisons on any list of 10 values, whether the list starts shuffled or already in order.

Putting things in order

Sorting means rearranging a list so its values go from smallest to largest (or by name, date, price, any order you can compare). It is one of the most common jobs a computer does: the contacts on a phone, search results ranked by relevance, a spreadsheet column sorted by date. Sorting also makes other jobs easier. As the last unit showed, a sorted list can be searched with binary search, and duplicates in a sorted list sit next to each other.

This unit covers three simple methods. All three work by comparing two values at a time and moving values around inside the same list. They are short to write and easy to follow, and all three slow down sharply on long lists. Watching why they slow down is the best preparation for the faster methods in the next unit. Throughout, we count two things: comparisons (asking "is this value bigger than that one?") and swaps (exchanging two values).

Bubble sort: swap neighbours that are out of order

Bubble sort walks along the list comparing each pair of neighbours. When the left one is bigger, it swaps them. After one full pass, the largest value has been carried step by step to the far right, like a bubble rising, and it never needs to move again. The next pass can stop one place earlier. A common improvement is to watch for a pass with no swaps at all: that means everything is already in order, so the sort can stop early.

Follow it on the list [5, 1, 4, 2, 8]. The first pass compares 5 and 1 (swap), 5 and 4 (swap), 5 and 2 (swap), 5 and 8 (leave): the list is now [1, 4, 2, 5, 8] and 8 is in place. The second pass compares 1 and 4, 4 and 2 (swap), 4 and 5, giving [1, 2, 4, 5, 8]. The third pass compares 1 and 2, then 2 and 4, makes no swap and stops. Total: 4 + 3 + 2 = 9 comparisons and 4 swaps.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // swap
        swapped = true;
      }
    }
    if (!swapped) break;  // already sorted
  }
  return a;
}

Selection sort: find the smallest, put it next

Selection sort works the way many people sort a hand of cards. Scan the whole list for the smallest value and swap it into the first position. Then scan the rest for the smallest remaining value and swap it into the second position, and so on. On [5, 1, 4, 2, 8] the first scan finds 1 and swaps it with 5; the second finds 2 and swaps it with 5; the last two scans find 4 and 5 already in place. That is only 2 swaps, but the scans still compare 4 + 3 + 2 + 1 = 10 times.

Selection sort never stops early. Even on a list that is already sorted, it still has to check every remaining value to be sure it has the smallest. For n values the comparisons always add up to (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. For 10 values that is 45; for 100 values, 4,950; for 1,000 values, 499,500. Its strength is the small number of swaps: at most n − 1, which matters when moving a value is expensive.

Insertion sort: slide each new value into place

Insertion sort keeps the left part of the list sorted and grows it one value at a time. It takes the next value and moves it left, swapping with its neighbour, until the neighbour is not bigger. Then that value is in place among the sorted ones. On a list that is already nearly in order, each new value moves only a step or two, so insertion sort is very quick there. On [5, 1, 4, 2, 8] it makes 7 comparisons and 4 swaps.

Counting the swaps: inversions

There is a neat way to predict how many swaps bubble sort and insertion sort need. Count the inversions: pairs of values that are in the wrong order relative to each other. In [5, 1, 4, 2, 8] the inversions are (5, 1), (5, 4), (5, 2) and (4, 2), four in all. Each swap of two neighbours that are out of order fixes exactly one inversion and creates none, so both methods make exactly 4 swaps. A reversed list of n values has every pair inverted, n(n − 1)/2 inversions, which is the worst case.

Each cell gives comparisons / swaps. The example list is [5, 1, 4, 2, 8]. Bubble sort here is the version that stops after a pass with no swap.

All three methods share the same weakness. In the worst case each one compares roughly every pair of values, about n²/2 comparisons. Double the list and the work goes up four times. Ten times the list means a hundred times the work. For a few dozen values that hardly matters; for a million it is hopeless, and the next unit shows how to do far better.