## Algorithm

for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
*→ invariant: a[k] smallest of a[i..n]*
swap a[i,k]
*→ invariant: a[1..i] in final position*
end

## Properties

- Not stable
- O(1) extra space
- Θ(n
^{2}) comparisons
- Θ(n) swaps
- Not adaptive

## Discussion

From the comparions presented here, one might conclude
that selection sort should never be used. It does not
adapt to the data in any way (notice that the four
animations above run in lock step), so its runtime
is always quadratic.

However, selection sort has the property of minimizing
the number of swaps. In applications where the cost of
swapping items is high, selection sort very well may be
the algorithm of choice.

## Key

- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.