pick the biggest, repeat

say you want your most played artists in order:

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.

#in code

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 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. O(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 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.