Selection sort divides the array into a sorted prefix and an unsorted suffix. On each pass it scans the unsorted suffix to find the smallest value, then swaps it into the first unsorted position. The sorted prefix grows by one, the unsorted suffix shrinks by one, and after n−1 passes the array is sorted.
Press play, or step through it one comparison at a time. Orange highlights the comparison, yellow is a swap, and green marks values locked into their final position.
Ready. 14 values, unsorted.
0 comparisons · 0 swaps
Ready. 14 values, unsorted.
- Comparing
- Swapping
- Sorted
Code
- def selection_sort(a):
- n = len(a)
- for i in range(n - 1):
- min_idx = i
- for j in range(i + 1, n):
- if a[j] < a[min_idx]:
- min_idx = j
- if min_idx != i:
- a[i], a[min_idx] = a[min_idx], a[i]
- return a
Try Worst case to see every pass do a swap, then Best case to see the same
number of comparisons but zero swaps. Selection sort always does n(n−1)/2
comparisons regardless of input order — only the swap count changes.
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n²) | Already sorted. Still scans the full suffix every pass (no early exit). |
| Average | O(n²) | Random order. Always n(n−1)/2 comparisons. |
| Worst | O(n²) | Reverse sorted. Same comparisons, maximum swaps (n−1). |
| Space | O(1) | Sorts in place. Only a temporary for the swap. |
| Stable | No | The swap can move equal values past each other. |
The key insight: selection sort’s comparison count is fixed at n(n−1)/2 regardless of input, but its swap count is at most n−1 — the lowest of any comparison sort. That makes it attractive when writes are expensive and reads are cheap.
Step by step
- Set
i = 0. Everything beforeiis sorted; everything fromionward is unsorted. - Scan from
i + 1to the end, tracking the index of the smallest value (min_idx). - If
min_idx ≠ i, swapa[i]anda[min_idx]. - Increment
i. The value atiis now in its final position. - Repeat until
i = n − 1. The last value is necessarily correct.
Worked example
Sorting [5, 2, 4, 1]:
| Pass | Minimum found | Swap | Result | What happened |
|---|---|---|---|---|
| 1 | 1 at index 3 | swap with index 0 | [1, 2, 4, 5] | Scanned all four, found 1 is smallest. |
| 2 | 2 at index 1 | no swap needed | [1, 2, 4, 5] | 2 is already in position. |
| 3 | 4 at index 2 | no swap needed | [1, 2, 4, 5] | 4 is already in position. |
Four values, six comparisons (always), one swap. Compare that with bubble sort on the same input, which does six comparisons and six swaps.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| Writes are expensive (flash, EEPROM, network) and you want minimal swaps | The input is large — O(n²) comparisons are unavoidable |
| You are teaching or learning how comparison sorts work | The data is nearly sorted — insertion sort would be O(n) |
| The input is tiny and simplicity matters more than speed | You need a stable sort |
| You want a predictable, always-the-same-cost algorithm | You want the fastest general-purpose sort — use quicksort or merge sort |
The code
Every version below is the standard in-place selection sort. Find the minimum, swap it to the front of the unsorted section, repeat.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]
return a
nums = [5, 1, 4, 2, 8]
selection_sort(nums)
print(nums)
Common questions
What is the time complexity of selection sort?
O(n²) in every case. It always scans the entire unsorted suffix to find the minimum, regardless of input order. There is no early exit and no adaptive shortcut.
Is selection sort stable?
No, not in its standard form. The swap at the end of each pass can move a value past an equal one. For example, sorting [2a, 2b, 1] swaps 2a with 1, placing 2a after 2b. A linked-list variant can be made stable, but the array version shown here is not.
Why is it called selection sort?
Because of what the animation shows. On each pass the algorithm selects the smallest remaining value and moves it into place. The act of choosing — selecting — the minimum is the defining step.
How is selection sort different from insertion sort?
Both are O(n²), but they differ in two important ways. Insertion sort is adaptive: nearly-sorted input finishes in O(n). Selection sort always does the same number of comparisons. On the other hand, selection sort does at most n−1 swaps total, while insertion sort may shift O(n²) values. If writes are expensive (flash memory, network), selection sort wins on data movement.
Should I use selection sort in real code?
Rarely. Your language’s built-in sort is O(n log n) and heavily optimised. Selection sort’s one practical niche is when the number of writes must be minimised — for example, sorting a small array stored on EEPROM where each write costs a wear cycle.
Does selection sort ever beat insertion sort?
On data movement, yes. Selection sort does at most n−1 swaps regardless of input, whereas insertion sort can do up to n(n−1)/2 shifts on reverse-sorted input. On comparisons they are tied at O(n²) in the worst case, but insertion sort wins on nearly-sorted input because it can stop scanning early.