Selection Sort Explained: Algorithm, Code & Complexity

Selection sort builds the sorted array one element at a time: it scans the unsorted region to find the smallest element, then swaps that element into the front of the unsorted region. Repeat, and the sorted prefix grows by one each round. Its defining trait is that it makes the fewest swaps of any common sort — exactly n - 1 — even though it does many comparisons.

The idea

Split the array into a sorted prefix (initially empty) and an unsorted suffix (initially everything). On each round, find the minimum of the suffix and swap it with the first unsorted slot. That slot now belongs to the sorted prefix.

Tracing [5, 1, 4, 2] ascending: round 1 finds min 1, swaps with index 0 → [1, 5, 4, 2]; round 2 finds min 2 in the suffix, swaps with index 1 → [1, 2, 4, 5]; round 3 finds min 4, already in place. Done.

Implementation

void selectionSort(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        std::swap(a[i], a[minIdx]);
    }
}

void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
    }
}

function selectionSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++)
      if (a[j] < a[minIdx]) minIdx = j;
    [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
}

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

Complexity

• Space: O(1) — in-place.
• Swaps: exactly n - 1, the fewest of any comparison sort.
• Stable: no. The long-distance swap can leapfrog an equal element over another. For example [2a, 2b, 1] becomes [1, 2b, 2a], flipping the two 2s.

Gotcha: Selection sort never speeds up on sorted input — unlike bubble sort and insertion sort, it has no O(n) best case, because it must scan the whole unsorted region every round to be sure it found the minimum.

When to use it

When writes are expensive and reads are cheap — selection sort minimizes the number of swaps (O(n) writes vs O(n²) for bubble sort), which matters for things like flash memory with limited write cycles. Otherwise its lack of an early exit makes insertion sort the better simple sort. See the full comparison.

Next: Insertion Sort.