Selection sort

Selection sort sorts a list the way many people sort a hand of cards: find the smallest, put it first, then find the smallest of the rest. It makes many comparisons but very few swaps, and its running time hardly depends on the order of the list.

Bars of different heights being sorted, the sorted part on the left, the smallest remaining bar highlighted and an arrow showing it swap into place
Bars of different heights being sorted, the sorted part on the left, the smallest remaining bar highlighted and an arrow showing it swap into place

The idea

Split the list into a sorted part on the left, empty at first, and an unsorted part on the right. Scan the unsorted part and remember where its smallest value is. Swap that value with the first unsorted value: the sorted part has grown by one. Repeat until only one value is left, which must be the largest.

An example

Take 5, 1, 4, 2, 8. The first pass scans all five values, finds 1 as the smallest, and swaps it with 5: 1, 5, 4, 2, 8. The second pass scans 5, 4, 2, 8, finds 2 and swaps it with 5: 1, 2, 4, 5, 8. The third pass finds 4 already in place, and the fourth finds 5 already in place, so nothing moves. That is 4 + 3 + 2 + 1 = 10 comparisons and only 2 swaps. Bubble sort needs 4 swaps on the same list.

Always the same number of comparisons

To be sure which value is the smallest, the scan has to look at every value that is left. Pass 1 makes n − 1 comparisons, pass 2 makes n − 2, and so on down to 1, which adds up to n(n − 1)/2. This number does not depend on the list: a sorted list costs exactly as many comparisons as a reversed one. Selection sort has no early stop, because a scan that finds the smallest value already in front has learned nothing about the rest.

Few swaps

Each pass makes at most one swap, so selection sort never makes more than n − 1 swaps, and it skips the swap when the smallest value is already in place. Bubble sort and insertion sort make as many swaps as there are pairs out of order, which can be about n²/2. When writing a value is much more expensive than reading two, for example on memory that wears out with every write, the small number of swaps is an advantage.

Not stable

A sort is stable when equal values keep their original order. Selection sort is not, because a long-distance swap can carry a value past an equal one. In 2, 2, 1 the first pass swaps the first 2 with the 1, giving 1, 2, 2 with the two 2s now in the opposite order. A version that shifts the values between instead of swapping is stable, but it moves far more values.

Explore it

Open the app and press Play, or press Step to go one comparison at a time. The value being scanned is highlighted, the smallest value so far has its own colour, and each pass ends with a swap into the sorted part on the left. Try a sorted list and a reversed list: the comparisons come out the same, only the swaps differ.

Frequently asked questions

What is the time complexity of selection sort?

O(n²) in every case: exactly n(n − 1)/2 comparisons for n values, whatever their order. It makes at most n − 1 swaps and needs only O(1) extra memory.

What is the difference between selection sort and bubble sort?

Bubble sort swaps neighbours as it goes and can stop early once a pass makes no swaps. Selection sort only remembers where the smallest value is and makes one swap at the end of each pass. Selection sort makes fewer swaps; bubble sort is faster on lists that are nearly sorted.

Is selection sort stable?

No. A swap can move a value past another value equal to it, so equal values can change order. It can be made stable by shifting values instead of swapping, which costs more moves.

What is heap sort's connection to selection sort?

Heap sort is a selection sort with a faster way to find the next value: it keeps the unsorted part in a heap, so each selection takes about log n steps instead of a full scan. That brings the total down to O(n log n).

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try selection sort