# Selection Sort

# Selection Sort

Selection sort divides the array into a sorted prefix and an unsorted suffix. At each step, it selects the smallest element from the unsorted portion and swaps it into the next position of the sorted prefix.

Unlike bubble-based methods, it performs a fixed number of swaps, which can be useful when swaps are expensive.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

## Algorithm

For each position $i$, find the minimum element in the range $[i, n-1]$ and swap it with $A[i]$.

```id="u2k7p4"
selection_sort(A):
    n = length(A)
    for i from 0 to n - 1:
        min_index = i
        for j from i + 1 to n - 1:
            if A[j] < A[min_index]:
                min_index = j
        swap(A[i], A[min_index])
```

## Example

Let

$$
A = [64, 25, 12, 22, 11]
$$

Step 1:

Minimum in $[0..4]$ is $11$

→ [11, 25, 12, 22, 64]

Step 2:

Minimum in $[1..4]$ is $12$

→ [11, 12, 25, 22, 64]

Step 3:

Minimum in $[2..4]$ is $22$

→ [11, 12, 22, 25, 64]

Sorted result:

$$
[11, 12, 22, 25, 64]
$$

## Correctness

After iteration $i$, the smallest element among indices $i$ through $n-1$ is placed at position $i$. This maintains the invariant that the prefix $A[0..i]$ is sorted and contains the smallest $i+1$ elements. Repeating this for all positions yields a fully sorted array.

## Complexity

| case    | comparisons        | time     |
| ------- | ------------------ | -------- |
| best    | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| worst   | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
| average | $\frac{n(n-1)}{2}$ | $O(n^2)$ |

Space complexity:

$$
O(1)
$$

## Properties

* in-place
* not stable in standard form
* minimizes number of swaps

## When to Use

Selection sort is useful when swap operations are expensive but comparisons are cheap. It guarantees at most $n-1$ swaps, which can be advantageous in constrained environments.

## Implementation

```id="m4x8q2"
def selection_sort(a):
    n = len(a)
    for i in range(n):
        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]
    return a
```

```id="k7p2z5"
func SelectionSort[T constraints.Ordered](a []T) {
    n := len(a)
    for i := 0; i < n; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[minIdx] {
                minIdx = j
            }
        }
        a[i], a[minIdx] = a[minIdx], a[i]
    }
}
```