Selection Sort divides the array into a sorted and unsorted region. On each pass it scans the unsorted region to find the minimum element and swaps it into the correct position. It always makes exactly O(n²) comparisons regardless of input, but only O(n) swaps — useful when writes are expensive.
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}
}Selection Sort scans the entire unsorted portion of the array to find the smallest element, then swaps it into position i. After i iterations, the first i elements are sorted.
Selection Sort makes at most n-1 swaps — the fewest of any simple sorting algorithm. This makes it attractive when write operations are costly, such as in flash memory.
Both best and worst cases are O(n²) comparisons since the inner loop always scans the full unsorted region. Space complexity is O(1) — fully in-place.
Selection Sort is not stable in its basic form. Equal elements can be reordered when a distant minimum is swapped past an equal element. A stable variant uses insertion instead of swapping.
What does Selection Sort do in each pass?
Selection Sort makes how many swaps in the worst case for n elements?
Is Selection Sort stable?