Thinking Recursively with Java

7.1. Selection Sorting

The selection sort algorithm is characterized by going through the elements of the array repeatedly, selecting the next value in sequence on each pass. On the first pass, the goal is to find the smallest value—in this case 63—which needs to appear in the initial position of the sorted array. Conceptually, one might view this step as removing an element from the original array and copying it to the beginning of a new array, like this:

On the next pass, one could identify the smallest remaining value and move it to the next position in newArray, as follows:

Repeating this process until each element has been moved into newArray results in a fully sorted array.

This conceptual model, however, is not well suited to implementation, primarily because the operation of removing an element from an array is not easily expressed in most programming languages. For this reason, it is useful to modify the algorithm so that, instead of removing an element, each pass through the array consists instead of exchanging the current element, moving left to right, with the smallest element in the remainder of the array.

To make the operation of the algorithm more concrete, imagine that you are using the index fingers of your left and right hands to mark two positions in the array. ...