Selection Sort: Pick the Minimum, Repeat

The Idea#

Selection Sort is what you'd do if someone dumped a pile of numbered cards on the table and asked you to sort them. You'd scan the whole pile, pick out the smallest card, set it down. Scan the rest of the pile, pick out the next smallest, set it down. Repeat. The algorithm has the same rhythm: find the minimum of the remaining elements, swap it into position, and move on. The "sorted region" on the left grows by exactly one element each pass.

---

How It Works#

On each pass, selection sort scans the unsorted portion of the array, finds the index of the smallest value, and swaps it with the first slot of that unsorted region. After pass k, the first k slots hold the k smallest values in sorted order.

The slot in accent is the current target, the position we're filling. The slot in success-green is the minimum we found during the scan. One swap per pass, no matter what.

---

The Algorithm#

1. Loop i from 0 to N - 2. Each iteration fills slot i.
2. Assume the minimum of the unsorted region is at index i. Scan i+1..N-1 to confirm or find a smaller one.
3. After the scan, swap arr[i] with arr[min_index].
4. The sorted prefix is now one element longer. Move on.
5. Stop when i = N - 1: the last element is already the largest by elimination.

---

Trace Through an Example#

Running selection sort on [5, 2, 4, 1, 3]:

Step	Action	Array State
Start	initial array	[5, 2, 4, 1, 3]
Pass 1	min of [5,2,4,1,3] is 1 → swap with index 0	[1, 2, 4, 5, 3]
Pass 2	min of [2,4,5,3] is 2 → already in place	[1, 2, 4, 5, 3]
Pass 3	min of [4,5,3] is 3 → swap with index 2	[1, 2, 3, 5, 4]
Pass 4	min of [5,4] is 4 → swap with index 3	[1, 2, 3, 4, 5]
Done	last slot is the max by elimination	[1, 2, 3, 4, 5]

Four passes, four scans, but only three swaps actually happened.

---

Complexity#

Case	Time	Why
Best	O(N²)	the inner scan always runs in full; no early exit possible
Average	O(N²)	same scan, same work
Worst	O(N²)	same scan, same work
Space	O(1)	in-place, single index variable

Selection sort always does the same number of comparisons regardless of input. There's no "lucky" input that runs faster. What it has going for it: it does at most N - 1 swaps, total. Every other comparison-based sort can do far more writes than that.

---

When Should You Use It?#

• Use it when writes are far more expensive than reads, such as sorting records in flash memory where each write contributes to wear, or any storage where rewriting a cell costs real money or lifespan.
• Use it in code-golf or embedded contexts where the implementation needs to be tiny and predictable. Selection sort's behavior is dead simple: same number of operations, every time.
• Don't use it for general-purpose sorting. O(N²) comparisons make it slower than insertion sort on most real inputs.
• The transferable pattern: "scan to find the extremum, then commit it" is the foundation of heap sort (use a heap instead of a linear scan) and of partial sorting / top-K problems.

---

Try It#

Let's take the example in the visualization below: [5, 2, 8, 1, 9, 3, 10, 4, 6, 7]. Three chips ride along the bars: i is the slot being filled, j is the scan position, and minIdx marks the smallest value found so far, jumping only when the decision panel reports a new minimum.

Pass 1 sweeps all nine remaining bars to discover that the minimum is 1 at index 3, then makes a single long swap into slot 0, which turns green. Pass 2 scans just as hard and swaps nothing, because 2 was already the smallest of what remained. Across the whole run: nine passes, 45 comparisons, and only seven actual swaps.

That ratio is the point of this algorithm. Watch how much of the runtime is the j chip sweeping and how little of it is bars actually moving. Selection sort pays a fixed O(N²) in reads to buy the fewest possible writes.