Implementation: Selection Sort Step

Implement finding the minimum index in a subarray.

Where used

Ensures that in-place mutations and index boundaries are handled before tackling more complex partitions.

Depth

A single step of selection sort receives a starting index. It searches the range from there, keeping track of the index of the smallest element found so far, and swaps this at the end of the search to the start. During the loop, minIndex always refers to the smallest position examined so far.

The loop starts at start plus one, because the starting element is already considered the preliminary minimum. An optional swap test avoids self-swapping. After the step, only the start position is guaranteed to be correct, not the entire remaining range.

Difficulty levels

1. Update minIndex over a subrange.
2. Specify the loop invariant of the minimum scan.
3. Embed the step into the complete outer sort loop.

Pitfalls

Anyone who swaps immediately for every smaller element implements a different and more write-intensive process. The search must also include the last array index.