Easy difficulty · Algorithm · Topics: sorting, comparison-sort, in-place
Selection sort builds the sorted array from left to right. In each round it scans the unsorted part to find the smallest element and swaps it into the first unsorted position. It always makes at most n - 1 swaps, which is the fewest of the simple sorts.
It is how many people sort a hand of cards laid out on a table: look through all the cards, pick the lowest, put it first; then look through the remaining cards and pick the lowest again. The sorted prefix only grows, and every element in it is already in its final place.
The invariant: nums[0..i-1] holds the i smallest values in sorted order. The remaining work is to choose the next smallest, which must be the minimum of nums[i..n-1].
i = 0 .. n - 2, treat nums[i..] as the unsorted part.minIndex = i.j = i + 1 .. n - 1; whenever nums[j] < nums[minIndex], set minIndex = j.minIndex is not i, swap nums[i] and nums[minIndex].Test case 0: nums = [64, 25, 12, 22, 11, 90, 3].
| i | Minimum found (index, value) | Array after the swap |
|---|---|---|
| 0 | (6, 3) | [3, 25, 12, 22, 11, 90, 64] |
| 1 | (4, 11) | [3, 11, 12, 22, 25, 90, 64] |
| 2 | (2, 12) | unchanged: already in place |
| 3 | (3, 22) | unchanged |
| 4 | (4, 25) | unchanged |
| 5 | (6, 64) | [3, 11, 12, 22, 25, 64, 90] |
Only three swaps were needed for seven elements, but all six scans still ran in full.
| Case | Time | Why |
|---|---|---|
| Best | O(n^2) | the scan for the minimum always visits the whole unsorted part |
| Average | O(n^2) | n(n-1)/2 comparisons regardless of the input order |
| Worst | O(n^2) | same number of comparisons; at most n - 1 swaps |
| Space | O(1) | in place, one extra variable |
n - 1 swaps.minIndex to 0 instead of i re-selects already sorted elements.i instead of i + 1 works but wastes a comparison.nums[i] with nums[j] inside the scan (instead of remembering minIndex) does many extra swaps and can break the logic.[3a, 3b, 1] becomes [1, 3b, 3a].i marks the start of the unsorted part; everything left of it is final.j scans to the right while minIndex stays on the best candidate so far; it jumps whenever a smaller bar is found.i and minIndex.Input: nums = [64, 25, 12, 22, 11, 90, 3]
Output: [3, 11, 12, 22, 25, 64, 90]
class Solution {
selectionSort(nums) {
const n = nums.length;
for (let i = 0; i < n - 1; i++) {
// Find the smallest value in the unsorted part nums[i..n-1].
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// Put it at the front of the unsorted part.
if (minIndex !== i) {
const temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
return nums;
}
}