Selection Sort

What is selection sort?

Selection sort fills the list from left to right. At each position it asks one question: which value belongs here? The answer is the smallest value that isn’t sorted yet. It finds that value, swaps it into place, and moves to the next position.

Think of lining people up by height. You scan the whole group for the shortest person, send them to the front, then scan everyone left for the next shortest.

It is easy to understand and it makes very few swaps. The catch is that it always scans everything that is left, even when the list is already sorted.

How it works, step by step

Press play above. Blue bars are being compared with the smallest value found so far. When a scan ends, the orange bars show the one swap that puts the smallest value in place, and it turns green.

1. Start at position i = 0. Assume the value there is the smallest: min_idx = i.
2. Scan every value to the right, from j = i + 1 to the end.
3. If a[j] is smaller than a[min_idx], remember j as the new smallest.
4. After the scan, swap a[i] with a[min_idx] (skip it if they are the same spot).
5. Move to i + 1 and repeat until the list is sorted.

In the code, the if a[j] < a[min_idx] line is the compare that lights up again and again. The swap line only fires once per position, at most. Watch the swap counter: it stays low even on the “reversed” preset.

Time and space complexity

The first scan looks at n − 1 values, the next at n − 2, and so on. That adds up to about n²/2 comparisons, every time, whatever order the list starts in. So selection sort is O(n²) in the best, average and worst case.

That makes it predictable, and also slow on input that is already sorted. Try the “nearly sorted” preset: the comparison count is the same as for a shuffled list of the same size. Bubble sort and insertion sort would finish much sooner there.

Swaps are where it shines. It makes at most n − 1 swaps, one per position. If writing to memory is much more expensive than reading, that can matter.

Space is O(1). It sorts in place and only remembers one index, min_idx.

Common mistakes

• Swapping inside the inner loop every time a smaller value appears. That turns it into a slower, messier sort. Remember the index during the scan, and swap once after it.
• Starting the inner loop at i instead of i + 1. It still works, but compares a value with itself for nothing.
• Assuming it is stable. It is not: the long-distance swap can jump a value over an equal one. For example [2a, 2b, 1] becomes [1, 2b, 2a].
• Expecting it to speed up on sorted input. It never does. There is no early exit to add.

When to use it

Rarely in real code. For almost any list, your language’s built-in sort is faster. Insertion sort beats it on small or nearly sorted lists.

Selection sort still makes sense when:

• Writes are costly and reads are cheap, like some flash memory, and you want the fewest swaps.
• You need the same running time on every input.
• You only want the few smallest values. Stop after k rounds and the first k positions hold them.

It is also the idea behind heap sort. Heap sort also picks the next value and puts it in place, but it keeps the rest in a heap, so finding that value takes O(log n) instead of a full scan. That one change takes the sort from O(n²) to O(n log n).

Questions

Is selection sort stable?

No. The swap that brings the smallest value forward can jump another value over an equal one, changing their order.

Why is selection sort O(n²) even on sorted input?

It has no way to know the rest is sorted. It must scan every remaining value to be sure it found the smallest one.

How many swaps does selection sort make?

At most n − 1, one per position. That is far fewer than bubble sort or insertion sort on a shuffled list.