Comparisons and Swaps

Analyze separately: Comparison (reading) and write/swap costs. Selection Sort: many comparisons, few swaps. Insertion Sort: many movements when unordered.

Where used

Cost model when comparisons are expensive (large objects, remote keys). Explains why keys are extracted or preprocessed in a Schwartzian-like manner.

Depth

The costs of sorting consist not only of comparisons. Depending on the data type, write accesses, copies, or movements can be significantly more expensive. Selection Sort examines the unsorted remainder completely but only moves elements at the end of the round. Insertion Sort can manage with few comparisons and movements on favorable inputs.

For Selection Sort, the lengths of the remaining elements add up as n minus one, n minus two, down to one. The number of movements grows significantly slower. This separation explains why a method can be interesting despite many key comparisons in expensive write media.

Difficulty levels

1. Count comparisons and data movements separately in one round.
2. Establish sums over shrinking remainder areas.
3. Select a method based on different cost models.

Pitfalls

A swap involves several write accesses and cannot be equated with a single comparison. Big-O alone obscures constant factors and differing operation costs.