# 6.2 Selection Sort

# 6.2 Selection Sort

Selection sort is the simplest sorting algorithm built around a clear global choice. At each step, it finds the smallest element in the unsorted suffix and moves that element into the next output position. The sorted prefix grows by one element per pass.

## Problem

You have an array `A[0..n-1]`. You want to sort it in nondecreasing order using only constant extra memory and a small number of swaps.

## Solution

For each index `i`, find the minimum element in `A[i..n-1]`, then swap it with `A[i]`.

```text
selection_sort(A):
  n = length(A)

  for i = 0 to n - 1:
    min_index = i

    for j = i + 1 to n - 1:
      if A[j] < A[min_index]:
        min_index = j

    swap A[i] and A[min_index]
```

## Example

Start with:

```text
[5, 2, 4, 1, 3]
```

The first pass scans the whole array and finds `1`. It swaps `1` into position `0`:

```text
[1, 2, 4, 5, 3]
```

The second pass scans from position `1` and finds `2`, which is already in place:

```text
[1, 2, 4, 5, 3]
```

The third pass scans from position `2` and finds `3`. It swaps `3` into position `2`:

```text
[1, 2, 3, 5, 4]
```

The last meaningful pass swaps `4` into position `3`:

```text
[1, 2, 3, 4, 5]
```

## Invariant

At the start of each outer-loop iteration with index `i`, the prefix `A[0..i-1]` is sorted and contains the `i` smallest elements of the original array.

This invariant is stronger than saying the prefix is sorted. It also says the prefix contains exactly the correct elements. That second part matters because a sorted prefix alone does not guarantee progress toward the final sorted array.

Initially, when `i = 0`, the prefix is empty, so the invariant holds. During one iteration, the algorithm finds the smallest element in the suffix `A[i..n-1]`. Since the prefix already contains the `i` smallest elements, this suffix minimum must be the next smallest element overall. After swapping it into position `i`, the prefix grows by one and still satisfies the invariant.

When the loop terminates, the prefix is the whole array. Therefore the whole array is sorted and contains exactly the original elements.

## Correctness

Selection sort preserves the permutation condition because it only swaps elements. A swap changes positions but does not create or remove values.

Selection sort establishes the order condition by repeatedly placing the next smallest remaining element at the boundary between the sorted prefix and the unsorted suffix.

After iteration `i`, every element in `A[0..i]` is less than or equal to every element in `A[i+1..n-1]`. Therefore no later operation needs to modify the prefix. The sorted part is final, not provisional.

## Complexity

Selection sort performs a fixed number of comparisons, regardless of input order.

For an array of length `n`, the number of comparisons is:

```text
(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2
```

So the time complexity is:

```text
O(n^2)
```

The algorithm uses constant extra memory:

```text
O(1)
```

The number of swaps is at most `n - 1`, which is much smaller than insertion sort in the worst case. This makes selection sort useful in rare situations where writes are expensive, although it remains too slow for large general-purpose sorting.

## Stability

Standard selection sort is not stable.

Consider:

```text
[(2, A), (2, B), (1, C)]
```

The minimum element is `(1, C)`, so the first swap produces:

```text
[(1, C), (2, B), (2, A)]
```

The two records with key `2` have changed relative order. The algorithm sorted by key, but it did not preserve stability.

A stable version can be written by removing the minimum element and shifting the intervening elements one position to the right, rather than swapping. That version preserves order among equal keys, but it increases the number of writes.

## Implementation Notes

Use selection sort only when the input is small, memory must be constant, and minimizing swaps is more important than minimizing comparisons. It is also useful as a teaching algorithm because the invariant is easy to state and verify.

Do not use selection sort for large arrays. Its comparison count remains quadratic even when the input is already sorted. Unlike insertion sort, it does not adapt to nearly sorted data.

## Common Bugs

A common off-by-one error is scanning only to `n - 2`, which misses the last element. Another common bug is swapping inside the inner loop whenever a smaller element appears. That changes the algorithm into a different procedure with more writes and a less clear invariant.

The inner loop should only update `min_index`. The swap belongs after the scan is complete.