Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Selection Sorting

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.