Selection Sort

Selection Sort searches for the minimum in the unsorted area and swaps it to the next position. After i steps, the first i positions are finalized.

Always $\Theta(n^{2})$ comparisons, few swaps (at most n).

Library sort for comparison: Sort an Array [1].

Where used

Only teaching and micro-cases. Demonstrates the selection idea; replace with library sorters in production.

Depth

Selection Sort divides the array into a sorted prefix and an unsorted remainder. In round i, the smallest element is searched in the remainder and placed at position i. After this, the prefix contains exactly the i plus one smallest values, counting duplicates.

The search for the minimum considers the remaining area regardless of how pre-sorted the input is. The number of actual swap operations, on the other hand, is bound to the number of rounds and can be omitted if the minimum is already in the front.

Difficulty levels

1. Execute one round with minimum index and subsequent swap.
2. Formulate the prefix invariant for correctness.
3. Assess comparison and writing costs separately.

Pitfalls

The found value alone is not sufficient because its index is needed for the swap. In the case of multiple minima, the choice of occurrence also affects the relative order of identical keys.