Work one through by hand
Sort [29, 10, 14, 37, 13].
Pass 1: min of all five is 10 → swap with 29 → [10, 29, 14, 37, 13]
Pass 2: min of last four is 13 → swap with 29 → [10, 13, 14, 37, 29]
Pass 3: min of last three is 14 → already in place → [10, 13, 14, 37, 29]
Pass 4: min of last two is 29 → swap with 37 → [10, 13, 14, 29, 37]
Four passes, 4 + 3 + 2 + 1 = 10 comparisons, and 3 swaps. The comparison count is fixed by the array size; only the swap count depends on the data.
Why it is quadratic no matter what
Pass 1 scans n elements, pass 2 scans n−1, and so on:
(n−1) + (n−2) + … + 1 = n(n−1)/2 → O(n²)
Critically this holds for every input. Finding a minimum requires examining every candidate, and the algorithm has no way to notice that the array is already sorted — it still scans the whole remaining region to confirm the minimum. Best case, average case and worst case are all Θ(n²), which makes selection sort strictly worse than insertion sort on nearly-sorted data.
The compensation is the write count. Selection sort performs at most n−1 swaps — O(n) writes, one per position. Insertion sort and bubble sort both perform O(n²) writes.
Find the smallest, put it in place, repeat
Selection sort scans the unsorted region for the smallest element and swaps it into the boundary position. The sorted region grows by one each pass.
Sorting [64, 25, 12, 22, 11]:
| Pass | Smallest found | Swap | Result |
|---|
| 1 | 11 | with 64 | [11, 25, 12, 22, 64] |
| 2 | 12 | with 25 | [11, 12, 25, 22, 64] |
| 3 | 22 | with 25 | [11, 12, 22, 25, 64] |
| 4 | 25 | already there | [11, 12, 22, 25, 64] |
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if arr[j] < arr[smallest]:
smallest = j
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
return arr
Note that the inner loop finds an index, not a value, and only one swap happens per pass. That is the algorithm's one genuine advantage.
The one thing it is good at
| Algorithm | Comparisons | Swaps / writes |
|---|
| Selection | O(n²) always | O(n) — at most n−1 |
| Bubble | O(n²) | O(n²) |
| Insertion | O(n²) | O(n²) shifts |
Selection sort performs at most n−1 swaps, whatever the input. Every other quadratic sort performs O(n²) moves.
That matters when writing is far more expensive than comparing:
- Flash memory and EEPROM, where each write consumes a limited erase cycle.
- Very large records moved by value rather than by pointer.
- Write-through caches or logged storage, where each write has a fixed overhead.
Outside those cases, its always-O(n²) comparison count makes it the weakest of the three. Insertion sort is O(n) on sorted input; selection sort is O(n²) on every input, because it always scans the whole unsorted region regardless of order.
Not adaptive, not stable
Two properties selection sort lacks, and both follow from how it works.
Not adaptive. The inner loop always scans everything. Sorted input takes exactly as long as random input — there is no early exit to add, because the algorithm cannot know the minimum without looking.
Not stable. The swap moves a distant element into position i, jumping over anything in between. Two equal elements can therefore be reordered:
Sorting [3a, 3b, 1] — pass 1 finds 1 and swaps it with 3a, giving [1, 3b, 3a]. The two equal 3s have swapped relative order.
A stable variant exists: instead of swapping, shift the intervening elements right and insert — but that reintroduces O(n²) writes, which was the only reason to use selection sort. The stable version has no advantage over insertion sort.
| Property | Selection | Insertion | Bubble |
|---|
| Adaptive | No | Yes | Yes |
| Stable | No | Yes | Yes |
| Swaps | O(n) | O(n²) | O(n²) |
| In place | Yes | Yes | Yes |
The one thing it is best at, and the one thing it gets wrong
Selection sort loses to insertion sort on almost every measure, so it is worth being precise about the single column where it wins -- and about the property it quietly lacks, which is the reason it is never the sort in a standard library.
Things to try
- Watch the scan, then the single swap. Set Array Size to 15 and press Next Step. Each pass sweeps the whole unsorted region looking for a minimum, then makes exactly one swap. The scanning is where all the time goes.
- Confirm the sorted region never changes. Once a cell joins the sorted block on the left it is never touched again. Contrast with bubble sort, where elements keep moving until the very end.
- Give it sorted input and watch it not care. Press Randomize Array until the array looks close to ascending, then Auto-Run. The comparison count is identical to a shuffled array — only the swaps drop. No other sort on this track is this indifferent to its input.
- Count the swaps. Run a full sort at Array Size 30 and note the swap count stays at or below 29, while the comparison count climbs past 400. That ratio is the entire argument for using it.
The one situation where it wins
When writes are dramatically more expensive than reads, minimising them matters more than minimising comparisons. That is the case for EEPROM and flash memory, where each cell tolerates a limited number of erase cycles, and for any sort where moving an element means copying a large record rather than an integer.
Selection sort guarantees at most n−1 writes. Cycle sort pushes this to the theoretical minimum and is the specialist choice, but selection sort gets most of the benefit with far simpler code.
What trips people up
- Swapping on every comparison. The minimum’s index should be tracked through the scan and swapped once at the end. Swapping each time a smaller element appears turns the O(n) write advantage — the only reason to use it — back into O(n²).
- Assuming it is stable. It is not. Sorting [2a, 2b, 1] swaps the 1 with the first 2, putting 2b before 2a. Stability requires the shifting variant, which forfeits the low write count.
- Expecting sorted input to be fast. Unlike insertion sort, there is no early exit and no adaptivity. Sorted input costs exactly as many comparisons as random input.
- Skipping the self-swap check. When the minimum is already in position the swap is a no-op; guarding it costs one comparison and saves a write, which matters given that low writes are the point.
The short version
Selection sort makes n−1 passes, each finding the minimum of what remains, giving Θ(n²) comparisons on every input and no benefit from partially sorted data. What it does offer is at most n−1 swaps — the fewest writes of any simple comparison sort. On ordinary in-memory data insertion sort beats it on every axis; on write-limited storage that swap count is the reason to choose it anyway.
Its useful relative: heap sort
Selection sort's structure — repeatedly extract the minimum — is exactly what a heap accelerates.
Finding the minimum by scanning is O(n), giving O(n²) overall. Finding it in a heap is O(log n), giving O(n log n).
That is heap sort: build a heap in O(n), then extract the extreme element n times. Same algorithm, better data structure, and it is genuinely competitive:
| | Selection sort | Heap sort |
|---|
| Find the extreme | O(n) scan | O(log n) heap |
| Total | O(n²) | O(n log n) |
| In place | Yes | Yes |
| Stable | No | No |
| Practical use | Rare | Introsort's fallback |
Heap sort is the guaranteed-O(n log n) fallback inside introsort, used when quick sort's recursion gets too deep. So selection sort's idea does appear in production — with a heap in place of the linear scan.
That progression is a good illustration of a general point: the algorithm and the data structure are separable, and improving the structure can change the complexity class without changing the logic.
Selection as a partial problem
Selection sort's first k passes give the k smallest elements, sorted. That makes it O(nk) for the top-k problem, which is better than O(n log n) sorting when k is very small.
Better options exist:
A heap of size k gives O(n log k) — push each element, pop when the heap exceeds k. This is what heapq.nlargest does.
Quickselect finds the k-th smallest in O(n) expected time using quick sort's partitioning, without sorting anything else.
So even for its natural partial-sorting niche, selection sort is dominated. The honest position: it is a teaching algorithm whose only real advantage is minimal writes, and that advantage matters in a narrow set of hardware situations.
Common mistakes
- Swapping inside the inner loop rather than after it, which turns the O(n) swap count into O(n²) and gives away the one advantage.
- Tracking the minimum value instead of its index, so the swap cannot be performed.
- Adding an early-exit flag, which cannot help — the algorithm has no way to detect sortedness.
- Expecting stability. It has none, and reordering equal elements can matter in multi-key sorting.
- Using it on real data.
sorted() is orders of magnitude faster.
Questions people ask
Why use selection sort at all? Only when writes are far more expensive than comparisons — flash memory, or moving very large records.
Is it stable? No. The long-distance swap reorders equal elements.
Why is it O(n²) even on sorted input? Because the inner loop must scan the whole unsorted region to know the minimum. Order is invisible to it.
How does it compare with bubble sort? Same comparisons, far fewer swaps, and no best case. Bubble sort is adaptive and stable; selection sort is neither.
What is heap sort's relationship to it? The same repeated-extraction idea with a heap instead of a scan, giving O(n log n).
Is it good for finding the k smallest? O(nk), which beats sorting for tiny k — and a size-k heap or quickselect beats it.
Recap in one screen
- Scan the unsorted region for the minimum, swap it into place, repeat.
- At most n−1 swaps — the only quadratic sort with linear writes.
- Always O(n²) comparisons: not adaptive, because it cannot detect sortedness.
- Not stable, because the swap jumps over intervening elements.
- Replace the linear scan with a heap and it becomes heap sort at O(n log n).