---
title: "Selection Sort"
description: "Find minimum, swap to front"
source: https://vizlearn.app/algorithms/sorting/selection-sort
---

# Selection Sort

Selection sort is a comparison-based sorting algorithm that repeatedly scans the unsorted portion of the array for its minimum value and swaps that value into the first unsorted slot. It runs in O(n²) time in every case, sorts in place with O(1) extra space, and performs at most n − 1 swaps.

Picture a coach lining up players by height with a clipboard: walk the whole line, note the shortest player left, and send exactly that one person to the front of the sorted group. One walk, one move. The clipboard does all the work — the comparisons are relentless, but the actual moving is almost free.

## How Selection Sort Works

Two nested loops and a running minimum. The outer loop counts the pass index `i` from 0 to n − 2; slot `i` is the next position to fill. At the top of each pass, `min_idx` is set to `i`. The inner loop sweeps `j` from `i + 1` to n − 1, and whenever `arr[j] < arr[min_idx]`, the clipboard updates: `min_idx = j`.

When the sweep ends, at most one swap moves `arr[min_idx]` into `arr[i]` — guarded by `if min_idx != i`, so a slot that already holds its minimum is left alone.

The invariant: after pass `i`, the first `i + 1` cells hold the `i + 1` smallest values in sorted order. The sorted region grows on the **left** — the mirror image of bubble sort, which settles its suffix on the right.

## Selection Sort Step by Step

The default input is `[25, 49, 25, 64, 12, 37, 15]`, and the two 25s are there on purpose.

Pass 1 (`i = 0`): `min_idx` starts at 0 (the first 25). Sweep right: 49 loses; the second 25 ties but a strict `<` doesn't beat a tie, so the pointer holds; 64 loses; then 12 at index 4 wins, and 37 and 15 can't beat it. Swap `arr[0]` with `arr[4]`: `[12, 49, 25, 64, 25, 37, 15]`. The 12 turns green — final position. But watch the two 25s: they went in as first-then-second (indices 0 and 2) and came out reversed, the first one flung clear past the second by that one swap. That is selection sort being **unstable**, and it happened on the very first move.

Pass 2 (`i = 1`): `min_idx` starts at 1 (value 49). The sweep passes 25, 64, the other 25, and 37 until 15 at index 6 takes the title. One swap: `[12, 15, 25, 64, 25, 37, 49]`. The price of that swap: 49 got flung from index 1 out to index 6, leapfrogging everything between.

Pass 3 (`i = 2`): the smallest of what's left is the 25 already sitting at index 2, so the pointer never moves and nothing swaps — a pass can lock a cell in place without touching the array.

The remaining passes repeat the rhythm — full sweep, at most one swap: pass 4 pulls the second 25 down to index 3 → `[12, 15, 25, 25, 64, 37, 49]`; pass 5 selects 37 → `[12, 15, 25, 25, 37, 64, 49]`; pass 6 selects 49 → `[12, 15, 25, 25, 37, 49, 64]`. Sorted.

In the animation, watch the `min` pointer chase the smallest bar across the unsorted region while `j` sweeps. A pass swaps at most once; when the minimum is already at `i`, the guard skips the swap. That occasional long-distance move is the visual signature separating selection sort from bubble sort's flurry of neighbor swaps.

## Time and Space Complexity

| Case | Time |
|---|---|
| Best | O(n²) |
| Average | O(n²) |
| Worst | O(n²) |

Space is O(1) — in place. The animated version is the standard guarded form (`if min_idx != i`), so already-placed minimums skip their swap.

The number worth memorizing is not the time complexity — it is the swap count: **O(n)**, at most one swap per pass, against n(n − 1)/2 comparisons always. When moving an element costs far more than comparing two (large records, slow storage), selection sort wins wall-clock fights against bubble and insertion sort despite the identical quadratic bound.

The price: it is not adaptive. A fully sorted input still gets the complete sweep treatment, every pass, every comparison. The clipboard trusts nothing.

## Edge Cases

- **Empty or one-element array** — the outer loop runs zero times.
- **Already sorted input** — every pass finds the minimum already at `i`, so the guard skips every swap; comparisons still cost the full O(n²).
- **All equal values** — `arr[j] < arr[min_idx]` never fires, `min_idx` never moves, no swaps at all.
- **Duplicates** — selection sort is **not stable**, and the default run shows it: the two 25s come in first-then-second and leave reversed, because pass 1's long swap jumps the first one clear past the second. Distilled: `[2a, 2b, 1]` sorts to `[1, 2b, 2a]`. When equal records must keep their input order, this is the property that rules selection sort out.

## Common Mistakes

- **Forgetting to reset `min_idx = i` at the top of each pass.** The clipboard carries last pass's answer and the algorithm hunts in the wrong region.
- **Comparing against `arr[i]` instead of `arr[min_idx]`.** You lose the running minimum and end up swapping with the first smaller value you see — a different (and wrong) algorithm.
- **Swapping unconditionally.** Without the `min_idx != i` guard, you pay for no-op swaps and bury the one-swap-per-pass property the algorithm exists to demonstrate.
- **Assuming stability.** Code that must keep equal records in order needs insertion sort, merge sort, or Timsort instead.