Sorting
Selection Sort
Divides the array into a sorted prefix and an unsorted suffix. Each pass selects the minimum of the unsorted part and swaps it into the next position of the prefix.
1Detailed explanation
Selection sort keeps a sorted prefix on the left. On each pass it scans the unsorted part to find the smallest value and swaps it into the first unsorted position.
It always performs n(n−1)/2 comparisons, even on already-sorted input, but makes at most n−1 swaps — handy when writing to memory is expensive.
The long-distance swap can move equal elements past each other, so the standard version is not stable.
2Pseudocode
procedure selectionSort(A)
n ← length(A)
for i ← 0 to n − 2
minIndex ← i
for j ← i + 1 to n − 1
if A[j] < A[minIndex]
minIndex ← j
if minIndex ≠ i
swap A[i] and A[minIndex]
return A3Interactive visualization
Divides the array into a sorted prefix and an unsorted suffix. Each pass selects the minimum of the unsorted part and swaps it into the next position of the prefix.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
const arr = [29, 10, 14, 37, 13];
console.log("Sorted:", selectionSort(arr));
5Time and space complexity
Time: Finding the minimum of the unsorted part always scans it completely, regardless of the input order: (n−1)+(n−2)+…+1 = n(n−1)/2 comparisons → O(n²) in every case. It performs at most n−1 swaps, which is useful when writes are expensive.
Space: Only the indexes i, j and minIndex are stored, and swapping happens inside the array, so auxiliary space is O(1).
6Common interview variations
- Find the k smallest elements with k passes (O(n·k)).
- Show an input where selection sort is not stable.
- Minimum number of swaps to sort an array (cycle decomposition).
- Double selection sort: place both the minimum and maximum each pass.