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.

Pass 1 — find min in [0..4], swap into index 052413swap min (1) into slot 0After pass 1 → [1, 2, 4, 5, 3] (1 is in its final position)

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.
python
Loading...

Trace Through an Example

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

StepActionArray State
Startinitial array[5, 2, 4, 1, 3]
Pass 1min of [5,2,4,1,3] is 1 → swap with index 0[1, 2, 4, 5, 3]
Pass 2min of [2,4,5,3] is 2 → already in place[1, 2, 4, 5, 3]
Pass 3min of [4,5,3] is 3 → swap with index 2[1, 2, 3, 5, 4]
Pass 4min of [5,4] is 4 → swap with index 3[1, 2, 3, 4, 5]
Donelast slot is the max by elimination[1, 2, 3, 4, 5]

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

Complexity

CaseTimeWhy
BestO(N²)the inner scan always runs in full — no early exit possible
AverageO(N²)same scan, same work
WorstO(N²)same scan, same work
SpaceO(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. But here's the redeeming property: 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 — for example, 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