Selection Sort

Overview

What this concept solves

Selection sort is the algorithm that says: I will not move anything until I know I'm moving it to its final home. Each round, it scans the unsorted region, finds the smallest value, and swaps it into the next sorted slot. After one round, position 0 holds the global minimum. After two rounds, positions 0 and 1 hold the two smallest. After n-1 rounds the entire list is sorted.

It's the dual of bubble sort. Bubble does many adjacent swaps to push one value to its final slot per pass. Selection does one swap per pass — at the very end of the scan, after the minimum is known. Both do O(n²) comparisons, but selection sort's defining feature is at most n-1 total swaps. That makes it the right choice on hardware where writes are far more expensive than reads — flash memory, write-once media, anything where you're literally counting writes.

The catch is selection sort doesn't get any faster on sorted data. The inner scan has to look at every remaining element to prove it found the minimum — that's true on random input, sorted input, and reverse-sorted input alike. So unlike insertion sort or bubble sort with early-exit, selection's best, average, and worst case are all O(n²). Predictable, but never fast.

Mechanics

How it works

One round

Assume the smallest value in the unsorted region is at position i (the leftmost unsorted slot).
Scan a[i+1] through a[n-1]. Each time you find a value smaller than the current min, update min_idx.
After the scan, swap a[i] with a[min_idx]. The slot at i is now locked.
Advance the sorted/unsorted boundary by one and repeat.

Across the whole list

Round 1 scans n-1 elements and locks position 0.
Round 2 scans n-2 elements and locks position 1.
Round k scans n-k elements; after round n-1, position n-1 is implicitly the largest.
Total comparisons: (n-1) + (n-2) + … + 1 = n(n-1)/2 ≈ n²/2.
Total swaps: at most n-1 (often fewer, since min_idx == i skips the swap).

Why writes-vs-reads matters

Reading from flash memory is fast and unlimited. Writing to flash wears the cells out — typical NAND survives ~100 000 writes per cell. If you're sorting on a device where every swap counts toward end-of-life, selection sort's n-1 swap budget is irresistible. Insertion sort can do O(n²) writes on bad input; selection sort can't.

Selection sort isn't stable

The swap at the end of each round can leap over equal-valued elements and reorder them. [3a, 3b, 2] selection-sorted becomes [2, 3b, 3a] — the two threes have flipped. If stability matters, use insertion sort or merge sort instead.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Selection Sort

About this simulation

Each round, the algorithm scans the unsorted right side for the smallest value (purple lift) and swaps it into the next sorted slot. Press Play to watch all eight rounds, Step / Back to walk through each comparison, Try sorted to confirm even sorted data still does n² compares, Shuffle for a new list.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through one full sort

Press Play. Watch the purple bar — that's the current minimum candidate during a scan. After the scan finishes, the purple bar swaps into the next green sorted slot. Notice how each round produces exactly one swap and how the sorted green region grows by one per round.

try 02

Count comparisons vs swaps

Use Step to advance manually. Watch the two counters in the stats grid. On 8 random items, expect ~28 comparisons but at most 7 swaps — the lopsided ratio that makes selection sort the write-efficient choice.

try 03

Try sorted data — same work, no savings

Press Try sorted. Step through. The algorithm still does ~28 comparisons — every round still has to scan the entire unsorted region to prove the smallest is at position i. The swap count stays at 0 since min_idx == i every round, but selection sort can never beat O(n²) the way bubble sort's early-exit can.

try 04

Shuffle and watch the swap discipline

Press Shuffle and step through. Each round picks one purple minimum, makes one swap, locks one slot. The total swap count never exceeds n-1, regardless of how scrambled the input is. That bound is selection sort's signature.

In practice

When to use it — and what you give up

When it's the right tool

Writes are expensive — flash storage, EEPROM, networked devices. n-1 swaps total beats every other in-place comparison sort.
You're teaching the divide-into-sorted-and-unsorted invariant — that mental model carries directly into insertion sort and heap sort.
Tiny n where you want predictable behaviour — selection sort's running time depends only on n, not on the input ordering. No surprises.
Finding the k smallest elements — stop after k rounds and you have a partial sort in O(k · n).

When to reach for something else

You need stability — selection sort isn't stable; merge or insertion is.
Performance matters at all — every comparison sort beats selection on random data; insertion sort beats it on nearly-sorted data.
Just use your language's sort() — for production code, the answer is always Timsort or intro-sort.

Pros

Minimum writes — exactly n-1 swaps in the worst case, often fewer. Unbeatable when writes hurt.
In-place — O(1) extra space.
Predictable runtime — O(n²) on every input, no surprises from worst-case inputs.
Simple to implement — one nested loop, one swap at the end of each round.
Easy to convert into a partial sort — stop after k rounds to get the k smallest values sorted.

Cons

O(n²) on every input — no fast path for sorted or nearly-sorted data.
Not stable — the end-of-round swap can hop over equal values.
Always n²/2 comparisons — even when the list is already sorted, every round still has to scan to prove the minimum.
Insertion sort dominates it for nearly all practical small-n use cases.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

selection-sort.ts

// Selection sort — minimum writes, O(n²) comparisons.
// In-place, not stable, predictable O(n²) on every input.
function selectionSort<T>(a: T[]): T[] {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    // Find the index of the smallest value in a[i..n-1].
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    // One swap per outer iteration — at most.
    if (minIdx !== i) {
      [a[i], a[minIdx]] = [a[minIdx], a[i]];
    }
  }
  return a;
}

// Example
selectionSort([29, 10, 14, 37, 13]);
// → [10, 13, 14, 29, 37]
// Comparisons: 4+3+2+1 = 10. Swaps: at most 4.

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

On a list of 100 elements, how many swaps does selection sort do in the worst case?

question 02 / 03

Why isn't there a meaningful 'best case' for selection sort?

question 03 / 03

Sorting `['3a', '3b', '2']` with selection sort yields `['2', '3b', '3a']`. What does that tell us?

0/3 answered