How selection sort works
- Take the first position as the place to fill, and assume its value is the smallest.
- Walk through the rest of the array. Whenever a smaller value turns up, remember its position.
- Swap the smallest value found into the place to fill.
- Move the place to fill one position to the right, and repeat until one value is left.
What the colours mean
The black bar is the smallest value found so far. Yellow is the value being compared with it, pink is a swap, and green bars are in their final place. Bars to the left of the current pass are already final.
Selection Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) | No |
Selection sort makes n(n - 1)/2 comparisons on every input, the same as bubble sort without an early exit: 45 for 10 values, sorted or shuffled.
Where it saves work is in writes. There is one swap per pass, so 10 values end at 18 writes whatever their order. This code swaps even when the smallest value is already in place, which is why the counter moves on a sorted array too.
The C# code
The listing beside the bars is the SortArray() method from Selection Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is selection sort stable?
Not in this form. The swap can carry a value past an equal one further right. Sorting 5, 5, 1 swaps the first 5 with the 1, and the two 5s change order.
When is selection sort a good choice?
When writes are expensive and the array is small. It never makes more than n - 1 swaps, far fewer than bubble sort or insertion sort need on a shuffled array.
Does selection sort run faster on a sorted array?
No. It has no way to notice that the array is sorted, so it makes the same n(n - 1)/2 comparisons.