Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Implementation

Program gif defines the StraightSelectionSorter class. This class is derived from the AbstractSorter base defined in Program gif and it provides an implementation for the no-arg sort method. The sort method follows directly from the algorithm discussed above. In each iteration of the main loop (lines 6-13), 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 9-11). That element is then moved into the correct position (line 12).

   program38728
Program: StraightSelectionSorter class sort method.

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 tex2html_wrap_inline57340 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, tex2html_wrap_inline58122 data comparisons are needed to sort the list.

The total running time of the straight selection sort method is tex2html_wrap_inline58122. Because the same number of comparisons and swaps are always done, this running time bound applies in all cases. That is, the best-case, average-case and worst-case running times are all tex2html_wrap_inline58122.


next up previous contents index

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