Selection Sort
Task: Sort this array in ascending order
Why we need Selection Sort
Analogy
- Imagine a basket of apples and you want them lined up smallest to largest.
- You look through the whole basket, pick out the smallest apple, and set it down at the start of the line.
- Then you look through everything still in the basket and do it again.
- You handle every apple many times, but you only ever move one per round. That is selection sort.
What is selection sort?
Definition
Selection sort repeatedly finds the smallest value in the unsorted part and puts it at the front of that part.
Each round scans everything still unsorted, remembering only where the smallest is, and finishes with a single swap.
The sorted part grows from the left, one value per round.
One round: scan everything, move one thing
Take 9 2 8 3 7. The round starts by assuming the first value is the smallest, then checks every other one against it.
2 is smaller, so the minimum moves there. 8, 3 and 7 are all bigger, so it stays. Only when the scan is over does anything actually move: 2 swaps with 9.
Notice what the inner loop is carrying. Not a value, and not a partial result: just an index, the place where the smallest thing has been seen so far.
The rounds, and what they cost
Two numbers matter here, and they behave very differently.
Comparisons are fixed. The scan looks at every remaining value whatever order they arrived in, so a sorted array costs exactly as much as a reversed one.
Swaps are tiny. One per round at most, so n - 1 for the whole sort, no matter what.
Try it
Try it yourself
Find the smallest, then move it once
Press sort on a few different shuffles and watch the two counters. The number looked at lands on the same total every time. The number moved never goes above seven.
Why it never gets faster
Bubble sort and insertion sort both finish early on data that is already in order. Selection sort cannot.
Watch out
Even on a sorted array, selection sort still scans the whole unsorted part every round to prove that the first value really is the smallest. There is nothing to detect and nothing to skip, so the best case, average case and worst case are all O(n2).
That is the trade it makes: it reads a lot and writes almost nothing.
In code
def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr print(selection_sort([5, 3, 8, 4, 2]))# [2, 3, 4, 5, 8]The inner loop only ever writes to min_idx. The array itself is untouched until the swap on the last line.
What it costs
| Case | Time | Space | Why |
|---|---|---|---|
| Best | O(n2) | O(1) | Sorted input still scans everything, so nothing is saved. |
| Average | O(n2) | O(1) | Every round scans the whole unsorted part. |
| Worst | O(n2) | O(1) | The same again. The order of the input does not matter. |
Space is O(1): it sorts in place, and the only thing it stores is one index.
Selection sort against the other two
| Selection sort | Insertion sort | Bubble sort | |
|---|---|---|---|
| The move | Scan for the smallest, then one swap | Lift a value and shift the bigger ones right | Compare neighbours and swap the pair |
| Best case | O(n2) | O(n) | O(n) |
| Swaps | At most n - 1 | None, it shifts instead | Up to about half of n squared |
| Good when | Writing is expensive | The data is nearly sorted | You are teaching sorting |
Note
That swap column is the one real argument for selection sort. If moving a value is expensive, and comparing two is cheap, doing the fewest possible moves is worth a lot of extra looking.
Where you have seen it
- Picking the smallest apple out of a basket, over and over
- Sorting books by height: find the shortest, put it at the start, repeat
- Any time you scan a whole list to find one thing before touching anything
Quick recap
- Scan the unsorted part for the smallest value
- Swap it into the front of that part
- Repeat with what is left
The sorted part grows from the left, one value per round, and the array is touched at most once each time.
Key takeaway
Look at everything, then move one thing. Repeat until there is nothing left to look at.