Selection Sort

Sorting and Searching · 20 min

Sorting · the fewest writes

Selection Sort,
one swap per pass.

Find the smallest value left, put it where it belongs, repeat. It is slow like bubble sort, but it writes to memory far less than bubble or insertion sort ever will — and that one strength costs you stability.

Run the selection simulation →
5 1 4 2
→
1 2 4 5 · 2 swaps

01 The idea

Sort the way you sort cards on a table

Spread a hand of cards face up. You scan the whole spread, pick out the lowest card, and lay it down at the left end. Then you scan again, ignoring the cards you have already placed. Selection sort is exactly that, written down: a sorted region that grows from the left, and an unsorted region that shrinks.

Find the smallest value in the part that is not sorted yet. Swap it into the first slot of that part. Repeat until one slot is left — that one is already correct by elimination.
Sorted prefixThe front of the array whose values are final. It grows by exactly one slot per pass and is never looked at again.
Unsorted suffixEverything behind the prefix. Each pass scans this part completely — there is no shortcut through it.
Minimum indexThe position of the smallest value seen so far in this pass. You remember where it is, not what it is, so you can swap it later.

02 Worked example

Selection sort on 5 1 4 2, by hand

Four numbers, three passes. Follow the 5: it starts at the front and gets pushed out of the way twice before it lands at the back. Each row below is the array after one full pass; green boxes are final, rose marks the value the swap displaced.

start5142smallest of all four is 1, at slot 1
pass 11542swap slots 0 and 1 · 3 comparisons
pass 21245smallest of 5 4 2 is 2 · swap slots 1 and 3
pass 312454 was already home · no swap at all
result12456 comparisons, 2 swaps, slot 3 never needed a pass

Count what that cost: 3 + 2 + 1 = 6 comparisons, and only 2 swaps. Slot 3 never got a pass of its own — once the other three slots were final, the largest value had nowhere else to be. That is the whole algorithm, and the code in the next section is these three passes written as two loops.

03 The code

Two loops, and the one line that saves the writes

Both versions below sort correctly and both make exactly the same 6 comparisons on 5 1 4 2. The only difference is how many times they write back into the array.

Naive · swap as you go

for i = 0 to n-2  for j = i+1 to n-1    if a[j] < a[i]      swap a[i], a[j]

Selection sort · min index

for i = 0 to n-2  min = i  for j = i+1 to n-1    if a[j] < a[min]      min = j  if min != i    swap a[i], a[min]

Remember the position, not the value. min holds where the smallest sits, so nothing is written while you are still looking. Pass 2 of the trace found the 2 sitting at the far end; remembering its slot brought it home in one write, while the left version needed two.

One write per pass, not one per improvement. The left loop swaps every time it meets something smaller, so the running minimum is stored inside slot i and has to be rewritten each time it improves. On 5 1 4 2 that is 4 swaps against 2 — with identical comparison counts.

if min != i skips a pointless self-swap. Pass 3 found 4 already sitting in slot 2. Without the guard you read a value and write it straight back over itself: three assignments that change nothing.

The outer loop stops at n-2. A final pass over one element would compare it to nothing. By elimination it is already the largest, so the line is free to delete.

05 Cheat sheet

Everything you need the morning of the interview

CaseCostWhy
Best — already sortedO(n²)Every pass still scans the whole unsorted suffix. There is no early-exit signal to find.
Average — random orderO(n²)Exactly n(n−1)/2 comparisons, always. For n = 4 that is 6.
Worst — reversedO(n²)Identical to the best case. Input order changes the swaps, never the comparisons.
Swaps — any inputO(n)At most n−1, one per pass — and with the if min != i guard from section 03, fewer whenever a value is already in place. Far below bubble sort’s n(n−1)/2 or insertion sort’s shifting.
Extra spaceO(1)One index variable and one temporary for the swap. It rearranges the original array.
Not stableA swap jumps a value across a long distance and can carry it past an equal value. 3a 3b 1 becomes 1 3b 3a.
Not adaptiveA sorted list costs the same as a reversed one. The pass structure does not depend on the data at all.
In placeNo second array, no recursion stack. Constant extra memory whatever n is.

06 Where & why

It is slow. Here is the one thing it is best at.

Selection sort is not the fastest sort and it is not the safest one to reach for. Its single real advantage is that it writes to memory fewer times than any of the sorts you are likely to reach for instead — bubble, insertion, merge, quick, heap — at most n−1 swaps, no matter how badly shuffled the input is.

Reach for it when…

Writes are expensiveThe array lives in flash or EEPROM where every write wears the cell out. Comparisons are free; writes are the budget.
Each element is a fat recordYou are moving 200-byte structs by value. A comparison reads one field, a move copies the whole thing.
The array is tiny and fixedTwenty items on a microcontroller, where a recursive sort’s stack frames cost more than the extra comparisons.
You only need the k smallestStop after k passes and the first k slots already hold the k smallest, in order. Each pass still scans the tail, but you never have to sort it — roughly k·n comparisons instead of n(n−1)/2.

Use something else when…

SituationBetter choiceWhy
The data is nearly sorted alreadyInsertion sortIt finishes in about O(n) on almost-sorted input. Selection sort still pays the full n(n−1)/2.
Equal keys must keep their original orderInsertion sort or merge sortBoth are stable. Selection sort’s long-distance swap can jump one equal value past another.
n is more than a few hundredYour language’s built-in sortTimsort and introsort run in O(n log n). At n = 1000 that is roughly 10,000 operations against 500,000.
You keep pulling the smallest from a changing setA min-heapEach extraction costs O(log n) instead of a fresh O(n) scan of everything left.
In real projects you will call the built-in sort. Selection sort earns its place because it makes one idea concrete — a sorted prefix that grows and an unsorted suffix that shrinks — and that same idea reappears in heap sort, in partial sorting, and in every interview that starts “sort this by hand”.

07 Interview questions

What they actually ask about selection sort

Twelve questions in the order an interview escalates. Say each answer out loud — every one should land in about twenty seconds.

What is selection sort?
You split the array into a sorted front and an unsorted back. Each pass scans the unsorted back, finds the smallest value in it, and swaps that value into the first unsorted slot. After n-1 passes the whole array is in order.
What is its time complexity?
O(n²) in the best, average and worst case. The comparison count is fixed at n(n-1)/2 — 6 for four elements — because pass i always looks at every element still unsorted. Only the swap count varies, and it never goes above n-1.
Why is the best case still O(n²) when bubble sort’s is O(n)?
Because selection sort has no signal it could stop on: to be sure a value is the smallest you must look at every remaining element, sorted input or not, so every pass runs to the end and the count stays n(n-1)/2. Bubble sort gets its O(n) best case from an extra flag — if a whole sweep makes no swaps, the array is provably sorted and it quits. Selection sort has nothing equivalent to test.
How many swaps does it perform?
At most n-1, one per pass. With the if min != i guard it does fewer whenever a value is already in place — on 5 1 4 2 it does 2, not 3. That is the fewest of any simple comparison sort, which is the whole reason to know it.
How much extra memory does it need?
O(1). One variable for the minimum’s index and one temporary for the swap, whatever the size of the array. Everything happens inside the original array, so it is an in-place sort with no recursion stack either.
Is selection sort stable?
No. A swap moves a value a long distance and can carry it past an equal value. Take 3a 3b 1: the first pass swaps 3a with 1 and you get 1 3b 3a, so the two 3s came out reversed. You can make it stable by shifting instead of swapping, but then you give up the n-1 write count.
Is it adaptive?
No. Adaptive means it runs faster when the input is partly sorted. Selection sort’s loop bounds depend only on n, never on the data, so a sorted list and a reversed list both cost n(n-1)/2 comparisons. Insertion sort is the adaptive one.
Selection sort or bubble sort — which would you pick?
Selection sort, almost always. Both do O(n²) comparisons, but bubble sort can perform up to n(n-1)/2 swaps against selection sort’s n-1. Bubble sort wins on exactly two points: it is stable, and with the early-exit flag it finishes an already-sorted array in O(n).
Selection sort or insertion sort?
Insertion sort on almost every input — it is stable, it is adaptive, and it drops to about O(n) on nearly-sorted data. Selection sort wins on writes only: insertion sort shifts elements constantly, so if a write costs far more than a comparison, the n-1 swaps win.
Why does the outer loop stop at n-2 instead of n-1?
Because once the first n-1 slots hold their final values, the one element left has nowhere else to go — it is the largest by elimination. A final pass would scan a single element and compare it to nothing, so the iteration is free to delete.
When would you actually use it in production?
Almost never. You call the language’s built-in sort, which runs in O(n log n). Selection sort turns up in embedded code where writes wear out flash memory, and in interviews. Claiming you use it at work is the quickest way to lose credibility.
How would you get the k smallest elements without sorting everything?
Run only k passes of selection sort and stop. The prefix is final after every pass, so the first k slots already hold the k smallest in order, at a cost of roughly k·n comparisons. A min-heap or quickselect beats it for large n, but this is the version you can write in thirty seconds.

08 Practice problems

Six problems to write yourself

The first five are variations on the two loops from section 03. Save the hard one for last — it throws the loops away entirely and connects selection sort to permutation cycles.

Count the writes

Easy
Given an array, return how many swaps selection sort performs when it uses the if min != i guard.
Follow-up
The answer is not always n-1. A pass contributes a swap only when the minimum was not already sitting in place, so you have to simulate rather than plug into a formula.
Show the hint
Increment your counter inside the guard, not once per pass.

Sort it descending

Easy
Rewrite the pass so the array ends up largest-to-smallest, and return the sorted array.
Follow-up
The comparison flips but the sorted prefix still grows from the left. Sorting ascending and reversing at the end does not count — the loop itself has to change.
Show the hint
Exactly one line of the inner loop is wrong for this job. Ask what the pass should be hunting for now, and leave the guard and the swap untouched.

Stop after k passes

Medium
Given an array and a number k, return the k smallest values in ascending order without sorting the rest of the array.
Follow-up
It tests whether you believe the prefix is genuinely final after each pass. If it is, you can walk away with the tail still in a mess and pay about k·n comparisons instead of n(n-1)/2.
Show the hint
The outer loop runs k times instead of n-1 times. Nothing inside it changes.

Make it stable

Medium
Modify selection sort so that equal values keep their original relative order, and return the sorted array.
Follow-up
Swapping is exactly what breaks stability, so the fix costs you the property the algorithm is famous for. State the new worst-case write count once you are done.
Show the hint
Instead of swapping the minimum into slot i, shift everything from slot i up to the minimum one place right and drop the minimum in.

Sort from both ends

Medium
In each pass find both the minimum and the maximum of the unsorted middle, place them at the left and right ends, and return the sorted array.
Follow-up
There is a bug waiting for you: if the maximum happens to sit in the very slot you just filled with the minimum, the second swap corrupts the array.
Show the hint
After the first swap, check whether the maximum’s index was the left slot; if it was, the maximum now lives where the minimum came from.

Minimum swaps to sort

Hard
Given an array of distinct values, return the smallest number of swaps that can sort it — computed directly, without running any sort.
Follow-up
Selection sort already achieves this minimum, but it needs O(n²) comparisons to find it. Convince yourself why every selection-sort swap splits one cycle of the permutation into two.
Show the hint
Map each value to the index it must end at. Follow that mapping from an unvisited index until it loops back to where you started — that is one cycle. Now work out what a single cycle of length L costs in swaps, and add the cycles up.