The third class of sorting algorithm that we consider comprises algorithms
that sort *by selection* .
Such algorithms construct the sorted sequence one element at a time
by adding elements to the sorted sequence *in order*.
At each step, the next element to be added to the sorted sequence
is selected from the remaining elements.

Because the elements are added to the sorted sequence in order, they are always added at one end. This is what makes selection sorting different from insertion sorting. In insertion sorting elements are added to the sorted sequence in an arbitrary order. Therefore, the position in the sorted sequence at which each subsequent element is inserted is arbitrary.

Both selection sorts described in this section sort the arrays
*in place* .
Consequently, the sorts are implemented by exchanging array elements.
Nevertheless, selection differs from exchange sorting
because at each step we *select* the next element of the sorted sequence
from the remaining elements
and then we move it into its final position in the array
by exchanging it with whatever happens to be occupying that position.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.