Selection sort
easyAlways exactly n−1 swaps, whatever the input - which makes it the right choice when writes are far more expensive than reads. The comparison count never changes either, so there is no best case to exploit.
O(n²)Average O(n²)Worst O(n²)Space O(1)Not stableIn placeSaved in this browser - no sign-up, nothing sent anywhere.
How selection sort works
Scan the unsorted region for its minimum, swap that minimum to the front, and the sorted prefix grows by one. After i rounds the leftmost i slots hold the i smallest values in their final positions - a cleaner invariant than bubble sort's, since finished elements never move again.
Its defining trait is the write bound: at most n - 1 swaps regardless of input, and this implementation even skips the swap when the minimum is already in place. Sorting 50 records costs at most 49 swaps. When writes are far more expensive than reads - flash memory with wear limits, records with heavy payloads - that bound is the whole reason to pick it.
The price is that comparisons never shrink. Round i scans the remaining n - i elements with no early exit, so sorted, reversed, and random input all cost exactly n(n-1)/2 comparisons - 120 for 16 values. There is no best case to exploit, and the long-range swap makes it unstable: an equal value can be thrown past its twin.
Step by step
- Sort [64, 25, 12, 22, 11]. Round 1 scans all five values; 11 at index 4 wins.
- Swap 11 with 64: [11, 25, 12, 22, 64]. Four comparisons, one swap, and index 0 is final.
- Round 2 scans the last four values; 12 beats 25 and swaps into index 1: [11, 12, 25, 22, 64].
- Round 3 scans three values; 22 beats 25 and swaps into index 2: [11, 12, 22, 25, 64].
- Round 4 compares 25 with 64 - 25 is already the minimum, so no swap is needed.
- Done: exactly 10 comparisons, the n(n-1)/2 it always pays, but only 3 swaps.
Complexity
| Best case time | O(n²) |
|---|---|
| Average time | O(n²) |
| Worst case time | O(n²) |
| Space | O(1) |
The inner loop has no early exit, so all three cases are Θ(n²).
Reference implementation
Python
def selection_sort(a):
n = len(a)
for i in range(n - 1):
lo = i
for j in range(i + 1, n):
if a[j] < a[lo]:
lo = j
if lo != i:
a[i], a[lo] = a[lo], a[i]
return aJavaScript
function selectionSort(a) {
const n = a.length;
for (let i = 0; i < n - 1; i++) {
let lo = i;
for (let j = i + 1; j < n; j++) if (a[j] < a[lo]) lo = j;
if (lo !== i) [a[i], a[lo]] = [a[lo], a[i]];
}
return a;
}Java
static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int lo = i;
for (int j = i + 1; j < a.length; j++)
if (a[j] < a[lo]) lo = j;
if (lo != i) { int t = a[i]; a[i] = a[lo]; a[lo] = t; }
}
}C++
void selectionSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int lo = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[lo]) lo = j;
if (lo != i) swap(a[i], a[lo]);
}
}Worth noticing
Exactly n-1 swaps, always
Watch the swap counter: it never exceeds n-1 regardless of the input. That makes selection sort the right choice when a write is far more expensive than a read - flash memory, or sorting records with huge payloads.
The comparison count never changes
Sorted, reversed, random - it always does n(n-1)/2 comparisons, because the inner loop has no early exit to take. Best, average and worst case are all Θ(n²).
It is not stable
The long-range swap can throw an equal value over another one. Sort [3a, 3b, 1] and 3a ends up after 3b.
Common pitfalls
- Swapping inside the inner loop every time a smaller value appears. Track the index and swap once after the scan - otherwise the n - 1 write bound, the algorithm's only selling point, is gone.
- Expecting stability. Sort [3a, 3b, 1]: the first swap sends 3a to the far end, past 3b. Equal values can reverse, which rules it out for multi-key sorts.
- Assuming sorted input is cheap. With no early exit, a sorted array still costs the full n(n-1)/2 comparisons - the counter here proves it.
- Skipping the lo != i guard and self-swapping. Harmless with a temp variable, but the XOR swap trick zeroes the element when both operands are the same slot.
- Scanning for the maximum but placing it at the front - direction mismatches produce a reversed array that looks confidently wrong.
Where it is used
- Write-limited hardware - EEPROM and flash - where at most n - 1 writes beats the thousands of shifts insertion sort might do.
- Sorting records with large payloads and cheap keys: comparisons are nearly free, moves are the cost that the swap bound caps.
- The conceptual base of heap sort, which runs the same extract-the-extreme loop but finds each extreme in O(log n) instead of O(n).
- The interview exercise for proving swap bounds and explaining why no early exit exists.
Frequently asked questions
What is the time and space complexity of selection sort?
O(n²) in the best, average, and worst case alike - the inner scan has no early exit, so 16 elements always cost 120 comparisons whatever their order. Space is O(1): it sorts in place, and the swap count is capped at n - 1.
Why is selection sort not stable?
The swap is long-range. Moving the minimum to the front can lift a value from the boundary and drop it far to the right, past elements equal to it. In [3a, 3b, 1], round one sends 3a beyond 3b. A stable variant must insert with shifts instead of swapping, giving up the write bound.
Why does selection sort make at most n - 1 swaps?
Each round places exactly one value into its final slot with at most one swap, and there are n - 1 rounds - the last element is correct by elimination. This implementation also skips the swap when the minimum is already in position, so the counter often reads lower.
Which is better, selection sort or insertion sort?
Insertion sort on almost every axis: it is stable, and it adapts - nearly-sorted input costs about n comparisons while selection sort still pays n(n-1)/2. Selection sort wins only when writes are the scarce resource, because n - 1 swaps beats insertion sort's potentially quadratic shift count.