Program defines the `StraightSelectionSorter<T>` class.
This class is derived from the abstract `Sorter<T>` base class
and it provides an implementation for `DoSort`.
The `DoSort` routine follows directly from the algorithm discussed above.
In each iteration of the main loop (lines 11-18),
exactly one element is selected from the unsorted elements
and moved into the correct position.
A linear search of the unsorted elements is done in order
to determine the position of the largest remaining element (lines 14-16).
That element is then moved into the correct position (line 17).

**Program:** `StraightSelectionSorter<T>` Class `DoSort` Member Function Definition

In all *n*-1 iterations of the outer loop are needed to sort the array.
Notice that exactly one swap is done in each iteration of the outer loop.
Therefore, *n*-1 data exchanges are needed to sort the list.

Furthermore, in the iteration of the outer loop,
*i*-1 iterations of the inner loop are required
and each iteration of the inner loop does one data comparison.
Therefore, data comparisons are needed to sort the list.

The total running time of the straight selection
`DoSort` routine is .
Because the same number of comparisons and swaps are always done,
this running time bound applies in all cases.
I.e., the best-case, average-case and worst-case
running times are all .

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