Selection sort, explained

Selection sort splits the list into a sorted part on the left and an unsorted part on the right. Each round it looks through the unsorted part, finds the smallest value and puts it at the end of the sorted part.

It makes very few swaps, which can matter when moving items is expensive.

How it works

• Look through the whole unsorted part and find the smallest value.
• Swap it with the first item of the unsorted part.
• The sorted part is now one item longer.
• Repeat until only one item is left.

A small example

Sort this list:

64 25 12 22 11

After round 1:  11 25 12 22 64
After round 2:  11 12 25 22 64
After round 3:  11 12 22 25 64
After round 4:  11 12 22 25 64

What to know about its cost

• Always O(n²) comparisons, even if the list is already sorted.
• At most n − 1 swaps.
• Uses O(1) extra space and is not stable.

Where it works well

• Very few swaps.
• Simple, with predictable behaviour.

Where it struggles

• No speed-up on sorted or nearly sorted lists.
• Slow for long lists.

Try it yourself

Open the Sorting experiment, enter the list 64 25 12 22 11, choose Selection Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment