Selection Sort

How it works, step by step

1. 1

   Look through the whole array and remember where the smallest value is.

2. 2

   Swap that smallest value with the value in the first position. The first slot is now final.

3. 3

   Look through the rest of the array (from position 2 onward) for the next smallest.

4. 4

   Swap it into the second position. That slot is final too.

5. 5

   Repeat. Each pass shrinks the unsorted part by one.

6. 6

   After n−1 passes, only one value is left - and it must be the biggest, so it is already in place.

The code, in JavaScript

function selectionSort(arr) {
  const a = [...arr];              // copy, so we don't change the input
  const n = a.length;

  for (let i = 0; i < n - 1; i++) {
    let min = i;                   // assume the first unsorted value is smallest

    // Scan the rest - did we assume wrong?
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[min]) min = j;
    }

    // Put the true smallest at position i.
    if (min !== i) {
      [a[i], a[min]] = [a[min], a[i]];
    }
  }

  return a;
}

selectionSort([5, 1, 4, 2]);       // → [1, 2, 4, 5]

Dry run: sorting [5, 1, 4, 2]

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• People expect the `swapped`-flag trick from bubble sort to work here. It does not: selection sort makes at most one swap per pass anyway, and the scan itself is the cost.
• Selection sort is not stable. Sorting [5a, 5b, 1] swaps 1 with 5a, giving [1, 5b, 5a] - the two fives changed order. If that matters, use insertion or merge sort.
• Do not swap inside the inner loop. The whole point is to scan first, swap once. Swapping every time you find a smaller value turns it into a worse bubble sort.
• The best case is O(n²) too. Bubble sort with early exit is O(n) on sorted input; selection sort never is. "Simplest" is not the same as "fastest".

Selection Sort vs. its closest relatives