Selection sort
Find the smallest value in the remaining region and swap it into the next position. Repeat until every value is in its final position.
Up to 24 values. Try duplicates or negative numbers.
Step 0 / 24: Original array. Find the minimum in the unsorted region.
Array: [5, 2, 4, 2, 1]
Comparisons: 0 · Writes: 0
Green: final sorted prefix. A highlighted single bar is the current minimum; two highlighted bars show a comparison or swap. Positions start at zero.
What stays sorted
After each pass, the prefix contains the smallest values in their final positions. Search for the next minimum only in the remaining region.
Why this sort is not stable
A distant swap can reverse equal values. Try [2, 2, 1]: swapping the first 2 with 1 moves it after the second 2. Choosing the first minimum does not prevent this.
Complexity
- Comparisons (any input order)
- n(n − 1) / 2
- Best, average and worst time
- Θ(n²)
- Swaps
- At most max(0, n − 1)
- Extra memory of the in-place algorithm
- O(1)
Each pass scans the entire remaining region, even when the array is already sorted. The comparisons add up to (n − 1) + (n − 2) + … + 1. If the minimum is already in place, the swap is skipped: sorted input makes zero writes, but still requires all comparisons.
The in-place algorithm needs constant extra memory. This visualizer stores Θ(n²) snapshots, each containing n slots: its history uses Θ(n³) memory. Inputs are limited to 24 values.
JavaScript implementation
This wrapper copies the input to preserve the original array, so the complete function additionally uses O(n) memory. Its loop performs the same comparisons and swaps as the demo.
function selectionSort(values) {
const result = [...values];
for (let start = 0; start < result.length - 1; start++) {
let minimum = start;
for (let i = start + 1; i < result.length; i++) {
if (result[i] < result[minimum]) minimum = i;
}
if (minimum !== start) {
[result[start], result[minimum]] = [result[minimum], result[start]];
}
}
return result;
}Compare three sorting algorithms
| Algorithm | Best time | Worst time | Stable | Array changes |
|---|---|---|---|---|
| Selection sort | Θ(n²) | Θ(n²) | No | At most n − 1 swaps |
| Insertion sort | Θ(n) | Θ(n²) | Yes | Shifts: up to Θ(n²) writes |
| Bubble sort | Θ(n) | Θ(n²) | Yes | Adjacent swaps: up to Θ(n²) writes |
Selection sort makes few swaps but does not benefit from an already sorted input. Insertion sort is useful for small, nearly sorted arrays. Bubble sort with early exit also detects sorted input, but may perform many adjacent swaps. All three have quadratic worst-case time.
Try [1, 2, 3, 4, 5] to compare comparisons and writes, [5, 4, 3, 2, 1] for reverse order, and [2, 2, 1] to follow equal values through a distant swap.
Video walkthrough
Built with AlgiViz
This website defines selection sort through AlgiViz array operations. Each comparison counts once and each swap counts as two array writes.