Sorting and Searching - Java Concepts - page 857

The selection sort algorithm sorts an array by repeatedly finding the smallest
element of the unsorted tail region and moving it to the front.

An obvious first step is to find the smallest element. In this case the smallest element
is 5, stored in a [3] . We should move the 5 to the beginning of the array. Of course,
there is already an element stored in a[0] , namely 11. Therefore we cannot simply
move a [3] into a[0] without moving the 11 somewhere else. We don't yet know
where the 11 should end up, but we know for certain that it should not be in a [0] .
We simply get it out of the way by swapping it with a [3] .

Now the first element is in the correct place. In the foregoing figure, the darker color
indicates the portion of the array that is already sorted.

Next we take the minimum of the remaining entries a[1] . . . a[4] . That
minimum value, 9, is already in the correct place. We don't need to do anything in
this case and can simply extend the sorted area by one to the right:

628
629

Repeat the process. The minimum value of the unsorted region is 11, which needs to
be swapped with the first value of the unsorted region, 17:

Now the unsorted region is only two elements long, but we keep to the same
successful strategy. The minimum value is 12, and we swap it with the first value, 17.

That leaves us with an unprocessed region of length 1, but of course a region of
length 1 is always sorted. We are done.