Selection Sort Visualization
Find the smallest thing, put it at the front, repeat on what remains. Selection sort is the sorting method humans instinctively use on a hand of cards, and it has one genuinely useful property: it performs at most n swaps total, which matters when writing is expensive and reading is cheap.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
void selectionSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) minIdx = j;
}
if (minIdx != i) {
int tmp = a[i];
a[i] = a[minIdx];
a[minIdx] = tmp;
}
}
}
int main() {
vector<int> a = {29, 10, 14, 37, 13};
selectionSort(a);
for (int x : a) cout << x << ' ';
return 0;
}Tracks the index of the minimum rather than its value, then performs at most one swap per outer iteration.
How it works, step by step
The array splits into sorted and unsorted
Everything before index i is finished and will never be touched again. Everything from i onward is the unsorted remainder. The outer loop grows the sorted prefix by exactly one element per iteration.
The inner loop only records a position
It does not move anything. It scans the unsorted remainder and remembers where the smallest value lives. Tracking the index rather than the value matters — you need to know where to swap from, not just what the minimum is.
One swap places the element for good
After the scan, a single exchange puts the minimum at index i and pushes whatever was there into the vacated slot. That element is now in its final position; no later pass can move it.
The last element is free
The outer loop runs to n - 1, not n. Once the first n-1 positions hold the n-1 smallest values in order, the single remaining element must be the largest and is already where it belongs.
The comparison count never changes
The inner loop always scans the entire remainder regardless of what it finds, so a sorted array and a reversed array cost exactly the same number of comparisons. There is no early exit to add — the algorithm has no way to know it is done.
Complexity
The nested scans always perform n(n-1)/2 comparisons because the inner loop cannot stop early; what it buys you is at most n-1 swaps, versus up to n squared for bubble sort, which matters when a write costs far more than a read.
Common bugs
Storing the minimum value instead of its index
int minVal = a[i]; then updating minVal in the loop leaves you with the right number and no idea where it came from. The swap needs a position. Track minIdx and read a[minIdx] when you need the value.
Forgetting to reset minIdx each pass
If minIdx = i sits above the outer loop, the second pass starts comparing against a stale position — usually an element already locked into the sorted prefix — so the scan finds nothing smaller and the array stops sorting after the first element. Step through pass two and watch minIdx never move.
Starting the inner loop at j = i instead of j = i + 1
It still produces a correct result, since comparing a[i] against itself changes nothing, but it wastes one comparison per pass. Harmless here, genuinely wrong if you later adapt the same loop shape to find a strict second-smallest.
Assuming selection sort is stable
It is not. Sorting the pairs (5a, 5b, 2) puts 2 at the front by swapping it with 5a, which throws 5a behind 5b and reverses their original order. If stability matters, use insertion sort or merge sort — no amount of tweaking the comparison fixes this, because the long-distance swap is the mechanism itself.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why does selection sort always take O(n squared) time?
Because the inner loop has to examine every remaining element to be sure it has found the minimum, and there is no way to conclude early. An already-sorted array still requires all n(n-1)/2 comparisons. Unlike bubble sort or insertion sort, it has no best case.
Is selection sort faster than bubble sort?
In practice usually yes, though both are O(n squared). Selection sort performs at most n-1 swaps while bubble sort can perform O(n squared) of them, and writes are typically more expensive than comparisons. Bubble sort only wins on data that is already nearly sorted, where its early-exit check finishes in one pass.
Is selection sort stable?
No. The swap moves the minimum across arbitrary distance, jumping it over elements equal to the one it displaces, which reverses their relative order. A stable variant exists that shifts elements instead of swapping, but then you have lost the low-swap-count advantage and effectively written insertion sort.
When would I choose selection sort?
When writes are far more expensive than reads — flash memory with limited write cycles, or sorting records that are costly to move. It guarantees at most n-1 writes to the array, a bound no comparison sort with better time complexity offers.