Selection Sort
See the smallest remaining element get found and swapped into place, one position at a time.
How it works
Selection sort splits the array into a sorted part on the left and an unsorted part on the right. On every pass it scans the whole unsorted part to find the smallest value, then swaps that value into the first unsorted position. That position is now final, and the sorted part grows by one.
Unlike bubble sort, it doesn't swap while scanning. It only remembers where the current minimum is, so it does at most n − 1 swaps in total.
When to use it
Selection sort never adapts to already-sorted input, but its small, predictable number of swaps can matter when writes are expensive, such as on flash memory. For everyday use, insertion sort or the built-in sort is the better choice.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(n²) | Even a sorted array is scanned every pass |
| Average | O(n²) | Random order |
| Worst | O(n²) | Any order: comparisons are always n(n−1)/2 |
It sorts in place with O(1) extra space. It is not stable: the long-distance swap can carry a value past an equal one. For example, sorting [5a, 5b, 1] swaps 5a with 1, giving [1, 5b, 5a].
Implementations
function selectionSort(array) {
const a = [...array];
for (let i = 0; i < a.length - 1; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
if (min !== i) [a[i], a[min]] = [a[min], a[i]];
}
return a;
}
def selection_sort(array):
a = list(array)
n = len(a)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if a[j] < a[smallest]:
smallest = j
if smallest != i:
a[i], a[smallest] = a[smallest], a[i]
return a
#include <utility>
#include <vector>
std::vector<int> selectionSort(std::vector<int> a) {
const int n = static_cast<int>(a.size());
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min]) min = j;
}
if (min != i) std::swap(a[i], a[min]);
}
return a;
}