Putting the Leaderboard in Order: Selection Sort

Put a time trial's leaderboard in order, fastest first, the way you'd do it by hand on a whiteboard, and count what that costs as the board grows: selection sort, and why it pays the same price even for a list that's already in order.

Apprentice · Data Structures · Updated

By

After this lesson you can

  • Trace selection sort pass by pass on a short list
  • Explain why selection sort is O(n²) however the list starts

Key takeaways

  • Selection sort finds the smallest item of the unsorted part, swaps it to the front of that part, and repeats until the whole list is sorted.
  • Each pass grows the sorted part on the left by one item.
  • It always makes n(n - 1) ÷ 2 comparisons, about n² ÷ 2, so it is O(n²) even on a list that's already sorted.
  • At 10,000 players that's about 50 million comparisons, paid again in full every time the board is sorted, even when only one score changed.

Before this: One Song in a Million, in 20 Looks: Binary Search (halving finds anything fast, but only in a sorted list).

A racing game has just finished a time trial, and six lap times are on the screen in the order the drivers crossed the line: 52, 38, 47, 31, 44 and 59 seconds. The leaderboard should show the fastest first. Nobody can find their place in a jumbled list, and the last lesson showed that a sorted list is also what makes searching fast. So: how do you put a list in order?

In real code you'll call your language's built-in sort, and the last lesson of this module shows how. But the choice of sort is the difference between a leaderboard that appears at once and one that hangs, and "sort this list without the built-in" is a favorite interview question. So first, the way you'd do it yourself.

What would you try?

Picture the six lap times on a whiteboard, with a clean column beside them for the leaderboard. You'd scan the whole list for the fastest time, 31, write it first and cross it out. Then you'd scan what's left for the fastest of those, 38, and write it second. Again and again, until nothing is left.

That's the plain try, and like checking every song in Is That Song in My Library? Linear Search, there's nothing simpler to knock down first: it's what almost everyone does by hand. So this lesson takes that one try, names it, and counts what it costs as the board grows.

How it got its name

A method that puts items in order is a sorting algorithm, and the whiteboard method is called selection sort: it selects the smallest item that's left, again and again. In a list there's no second whiteboard, so it works in place:

  • The list has a sorted part on the left, empty at first, and an unsorted part on the right.
  • Each pass scans the unsorted part for its smallest item and swaps it with the first item of the unsorted part.
  • The sorted part grows by one item per pass. After n − 1 passes, the last item is in place too.

Selection sort in code

This code sorts the lap times and prints the list after every pass:

int[] times = { 52, 38, 47, 31, 44, 59 };

for (int pass = 0; pass < times.Length - 1; pass++)
{
    int smallest = pass;
    for (int i = pass + 1; i < times.Length; i++)
    {
        if (times[i] < times[smallest])
        {
            smallest = i;
        }
    }
    (times[pass], times[smallest]) = (times[smallest], times[pass]);
    Console.WriteLine("Pass " + (pass + 1) + ": " + string.Join(" ", times));
}
Pass 1: 31 38 47 52 44 59
Pass 2: 31 38 47 52 44 59
Pass 3: 31 38 44 52 47 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
void main() {
    int[] times = {52, 38, 47, 31, 44, 59};

    for (int pass = 0; pass < times.length - 1; pass++) {
        int smallest = pass;
        for (int i = pass + 1; i < times.length; i++) {
            if (times[i] < times[smallest]) {
                smallest = i;
            }
        }
        int swap = times[pass];
        times[pass] = times[smallest];
        times[smallest] = swap;
        IO.println("Pass " + (pass + 1) + ": " + Arrays.stream(times).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
Pass 1: 31 38 47 52 44 59
Pass 2: 31 38 47 52 44 59
Pass 3: 31 38 44 52 47 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
times = [52, 38, 47, 31, 44, 59]

for pass_number in range(len(times) - 1):
    smallest = pass_number
    for i in range(pass_number + 1, len(times)):
        if times[i] < times[smallest]:
            smallest = i
    times[pass_number], times[smallest] = times[smallest], times[pass_number]
    print(f"Pass {pass_number + 1}: " + " ".join(str(time) for time in times))
Pass 1: 31 38 47 52 44 59
Pass 2: 31 38 47 52 44 59
Pass 3: 31 38 44 52 47 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
const times = [52, 38, 47, 31, 44, 59];

for (let pass = 0; pass < times.length - 1; pass++) {
  let smallest = pass;
  for (let i = pass + 1; i < times.length; i++) {
    if (times[i] < times[smallest]) {
      smallest = i;
    }
  }
  [times[pass], times[smallest]] = [times[smallest], times[pass]];
  console.log(`Pass ${pass + 1}: ${times.join(" ")}`);
}
Pass 1: 31 38 47 52 44 59
Pass 2: 31 38 47 52 44 59
Pass 3: 31 38 44 52 47 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59
const times: number[] = [52, 38, 47, 31, 44, 59];

for (let pass = 0; pass < times.length - 1; pass++) {
  let smallest = pass;
  for (let i = pass + 1; i < times.length; i++) {
    if (times[i] < times[smallest]) {
      smallest = i;
    }
  }
  [times[pass], times[smallest]] = [times[smallest], times[pass]];
  console.log(`Pass ${pass + 1}: ${times.join(" ")}`);
}
Pass 1: 31 38 47 52 44 59
Pass 2: 31 38 47 52 44 59
Pass 3: 31 38 44 52 47 59
Pass 4: 31 38 44 47 52 59
Pass 5: 31 38 44 47 52 59

A note on the languages: C#, Python, JavaScript and TypeScript can swap two items in one line, by assigning a pair to a pair. Java can't, so it parks one item in a variable, swap, while the other moves. Python's loop variable is pass_number, because pass is a word Python keeps for itself.

Read the passes slowly. Pass 1 swaps 31 to the front. In pass 2, 38 is already the smallest of the rest, so it swaps with itself and nothing moves. Pass 5 doesn't change anything either, but the code still has to check. After the last pass, 59 is in place without being touched: when every other time has been placed, the one that's left is the largest.

The six lap times 52, 38, 47, 31, 44 and 59 drawn as six cards in a row, shown six times: the starting order, then after each of the five passes. In each row the sorted part on the left is shaded, the smallest card that pass found is outlined, and an arrow shows the swap, until the row reads 31, 38, 44, 47, 52, 59

Why it's O(n²), every time

Count the comparisons, the times[i] < times[smallest] checks. Pass 1 compares the first time with the 5 others, pass 2 makes 4 comparisons, then 3, 2 and 1: 15 in all for 6 times. For n items it's (n − 1) + (n − 2) + … + 1, which is n(n − 1) ÷ 2, the pair count from Why the Duplicates Button Crawls: O(n²). Every pair of items is compared once.

Drop the small stuff, as in Are Two Loops Twice as Slow? Why O(2n) Is Still O(n), and that's O(n²), read "big O of n squared": double the lap times, about four times the comparisons. 1,000 times take 499,500 comparisons, and 2,000 take 1,999,000.

Where it breaks

Six times is 15 comparisons, nothing at all. But time trials run all day, and a busy game's board holds 10,000 players. Selection sort compares every pair once: 49,995,000 comparisons, about 50 million, to sort that board. Twice the players, four times the work: 20,000 players is about 200 million.

The catch is the word every. Selection sort can't tell that a list is already sorted, because the only way to know an item is the smallest is to compare it with all the rest. So a list that's already in order still takes all 15 comparisons:

int Comparisons(int[] start)
{
    int[] times = (int[])start.Clone();
    int comparisons = 0;
    for (int pass = 0; pass < times.Length - 1; pass++)
    {
        int smallest = pass;
        for (int i = pass + 1; i < times.Length; i++)
        {
            comparisons++;
            if (times[i] < times[smallest])
            {
                smallest = i;
            }
        }
        (times[pass], times[smallest]) = (times[smallest], times[pass]);
    }
    return comparisons;
}

Console.WriteLine("Shuffled: " + Comparisons(new int[] { 52, 38, 47, 31, 44, 59 }) + " comparisons");
Console.WriteLine("Already sorted: " + Comparisons(new int[] { 31, 38, 44, 47, 52, 59 }) + " comparisons");
Console.WriteLine("Backward: " + Comparisons(new int[] { 59, 52, 47, 44, 38, 31 }) + " comparisons");
Shuffled: 15 comparisons
Already sorted: 15 comparisons
Backward: 15 comparisons
int comparisons(int[] start) {
    int[] times = start.clone();
    int comparisons = 0;
    for (int pass = 0; pass < times.length - 1; pass++) {
        int smallest = pass;
        for (int i = pass + 1; i < times.length; i++) {
            comparisons++;
            if (times[i] < times[smallest]) {
                smallest = i;
            }
        }
        int swap = times[pass];
        times[pass] = times[smallest];
        times[smallest] = swap;
    }
    return comparisons;
}

void main() {
    IO.println("Shuffled: " + comparisons(new int[] {52, 38, 47, 31, 44, 59}) + " comparisons");
    IO.println("Already sorted: " + comparisons(new int[] {31, 38, 44, 47, 52, 59}) + " comparisons");
    IO.println("Backward: " + comparisons(new int[] {59, 52, 47, 44, 38, 31}) + " comparisons");
}
Shuffled: 15 comparisons
Already sorted: 15 comparisons
Backward: 15 comparisons
def comparisons(start):
    times = list(start)
    count = 0
    for pass_number in range(len(times) - 1):
        smallest = pass_number
        for i in range(pass_number + 1, len(times)):
            count += 1
            if times[i] < times[smallest]:
                smallest = i
        times[pass_number], times[smallest] = times[smallest], times[pass_number]
    return count


print(f"Shuffled: {comparisons([52, 38, 47, 31, 44, 59])} comparisons")
print(f"Already sorted: {comparisons([31, 38, 44, 47, 52, 59])} comparisons")
print(f"Backward: {comparisons([59, 52, 47, 44, 38, 31])} comparisons")
Shuffled: 15 comparisons
Already sorted: 15 comparisons
Backward: 15 comparisons
function comparisons(start) {
  const times = [...start];
  let count = 0;
  for (let pass = 0; pass < times.length - 1; pass++) {
    let smallest = pass;
    for (let i = pass + 1; i < times.length; i++) {
      count++;
      if (times[i] < times[smallest]) {
        smallest = i;
      }
    }
    [times[pass], times[smallest]] = [times[smallest], times[pass]];
  }
  return count;
}

console.log(`Shuffled: ${comparisons([52, 38, 47, 31, 44, 59])} comparisons`);
console.log(`Already sorted: ${comparisons([31, 38, 44, 47, 52, 59])} comparisons`);
console.log(`Backward: ${comparisons([59, 52, 47, 44, 38, 31])} comparisons`);
Shuffled: 15 comparisons
Already sorted: 15 comparisons
Backward: 15 comparisons
function comparisons(start: number[]): number {
  const times = [...start];
  let count = 0;
  for (let pass = 0; pass < times.length - 1; pass++) {
    let smallest = pass;
    for (let i = pass + 1; i < times.length; i++) {
      count++;
      if (times[i] < times[smallest]) {
        smallest = i;
      }
    }
    [times[pass], times[smallest]] = [times[smallest], times[pass]];
  }
  return count;
}

console.log(`Shuffled: ${comparisons([52, 38, 47, 31, 44, 59])} comparisons`);
console.log(`Already sorted: ${comparisons([31, 38, 44, 47, 52, 59])} comparisons`);
console.log(`Backward: ${comparisons([59, 52, 47, 44, 38, 31])} comparisons`);
Shuffled: 15 comparisons
Already sorted: 15 comparisons
Backward: 15 comparisons

The function sorts a copy, so the list it's given keeps its own order. That's the part that hurts a live leaderboard: when one new lap time arrives on a sorted board of 10,000, sorting again with selection sort costs the full 50 million comparisons, though only one time moved. The next lesson starts from exactly that problem.

Selection sort has one real strength: it makes at most one swap per pass, n − 1 in all. When moving an item is far more expensive than looking at it (rearranging heavy crates, or writing to slow storage), that can matter. On a computer's list it rarely does.

Try it. Add a seventh time, 40, to the first program. How many passes and comparisons does it take now? (6 passes, and 6 + 5 + 4 + 3 + 2 + 1 = 21 comparisons.)

The cost card

Operation Big-O The everyday reason
Sort, any starting order O(n²) each pass scans everything that's left to be sure it found the smallest
Swaps O(n) at most one swap per pass
Extra memory O(1) it sorts in place, remembering only where the smallest is

Check yourself

2 questions to try on the lesson page.

So what

Selection sort is the clearest way to see what sorting costs: comparing every pair is O(n²), and it pays that full price even for a list that's already in order. The next lesson, One New Score on a Sorted Leaderboard: Insertion Sort, starts from a board that's already sorted and gets one new score, and finds a way not to pay it all again.

Key terms

Cheat sheets