# pick the biggest, repeat

2023-10-29 · 3 min read · #algorithms

Source: https://jopcmelo.com/writing/pick-the-biggest-repeat

say you want your most played artists in order:

| artist                | plays |
| --------------------- | ----- |
| Van Halen             | 132   |
| The Rolling Stones    | 353   |
| Metallica             | 220   |
| Nirvana               | 185   |
| Aerosmith             | 157   |
| Led Zeppelin          | 238   |
| Red Hot Chili Peppers | 201   |

one way: go through the list, find the most played, and put it first. go through what's left, find the most played, put it second. **pick the biggest, repeat** until there's nothing left. that's selection sort.

*(sketch: five play counts. each pass circles the biggest one left, and it swaps places with the first unsorted one along two arcs, until the row reads 353, 220, 185, 157, 132. then it starts over)*

## in code

```javascript
function selectionSort(list) {
  for (let i = 0; i < list.length - 1; i++) {
    let biggest = i;
    for (let j = i + 1; j < list.length; j++) {
      if (list[j].plays > list[biggest].plays) biggest = j;
    }
    [list[i], list[biggest]] = [list[biggest], list[i]];
  }
  return list;
}
```

it sorts the list in place: everything before `i` is done, and each pass swaps the biggest of the rest into slot `i`. on the artists above, it gives The Rolling Stones, Led Zeppelin, Metallica, Red Hot Chili Peppers, Nirvana, Aerosmith, Van Halen. (there's [an older version in my algorithms repo](https://github.com/joaopcm/algorithms/blob/main/selection-sort/index.js) that builds a new array instead.)

## why it's O(n²)

the first pass looks at all `n` items, the next at `n - 1`, then `n - 2`, down to 2. that adds up to `n(n - 1) / 2` comparisons: for the 7 artists, 21. it shrinks every pass, but on average it's still half the list, `n` times, and [Big O drops the half](/writing/how-it-grows-not-how-fast). `O(n²)`.

*(sketch: a 7 by 7 grid of dots, one per pair of artists. the 21 above the diagonal are filled in: the pairs the sort compares. 21 comparisons of 49, about half, still n²)*

and it does all 21 every time. hand it a list that's already sorted, and it still compares every pair, because **it never checks whether it's done**.

you can feel the square when the list grows. on my machine (Node 24, a Ryzen 7 3700X), sorting 10,000 random numbers took 89ms, 20,000 took 411ms, and 40,000 took 2.1s. **double the list, and it takes four to five times as long.** [quicksort](/writing/pick-a-pivot) does the same job in `O(n log n)` on average.

## what it's still good at

it barely moves anything. at most one swap per pass, so `n - 1` swaps in total: the 7 artists took 5. when writing is much more expensive than reading, like on some flash memory, that can matter more than the comparisons.