Selection sort

For ascending order, a pass scans the unprocessed suffix, records the position of its smallest key, and exchanges it with the suffix’s first item. The next pass starts later, leaving a prefix containing the smallest items in final order.

A complete scan fixes one position without ordering the rest of the suffix. Unlike insertion sort, which places the next input item into a sorted prefix, selection sort searches all remaining candidates for the next output item. The growing ordered region hides different comparison and movement patterns.

References: [1]

The successive suffix scans sum to Θ(n²) comparisons. In the standard implementation, even sorted input still requires searching each remaining suffix rather than enjoying insertion sort’s linear best case.

There is at most one placement exchange per pass, giving a linear exchange count; some implementations include self-exchanges. Comparisons and writes are distinct costs when movement is expensive, although fewer exchanges alone do not imply a faster complete algorithm.

References: [2]

Ordinary exchange-based selection sort is unstable. Starting with labelled keys 2a, 2b, 1, the first exchange produces 1, 2b, 2a. Moving a different, smaller key reverses two equal records without directly comparing them as unequal.

A stable variant can select the leftmost minimum, remove it, and shift the preceding block right before inserting it. That changes movement costs. The low exchange count of the standard implementation therefore does not describe every stable selection-based variant.

References: [2] [3]