Selection sort

Selection sort thinks of the list as two parts: a sorted part on the left (empty at first) and an unsorted part on the right.

In each pass:

• find the smallest element in the unsorted part;
• swap it with the leftmost element of the unsorted part.

The sorted part grows by one element each time.

Example: in pass 1 on [8, 7, 13, 1, -9, 4], the smallest element is -9 (at index 4). It is swapped with 8 (at index 0), giving [-9, 7, 13, 1, 8, 4].

Like bubble sort, it needs n − 1 passes: by then, the last element is automatically in its correct place.

In Algorithm 5.2, a variable min remembers the position of the smallest element found so far, and a flag records whether a smaller one was found, so that a swap is made only when needed. So selection sort makes at most one swap per pass, far fewer swaps than bubble sort. But it still compares every unsorted element in every pass, not just neighbours.