Java Reference
In-Depth Information
Algorithm selectionSort(a, first, last)
// Sorts the array entries a[first] through a[last] recursively.
if (first < last)
{
indexOfNextSmallest = the index of the smallest value among
a[first], a[first + 1], . . . , a[last]
Interchange the values of a[first] and a[indexOfNextSmallest]
// Assertion: a[0] a[1] . . . a[first] and these are the smallest
// of the original array entries. The remaining array entries begin at a[first + 1].
selectionSort(a, first + 1, last)
}
After we place the smallest entry into the first position of the array, we ignore it and sort the
rest of the array by using a selection sort. If the array has only one entry, sorting is unnecessary. In
this case, first and last are equal, so the algorithm leaves the array unchanged.
8.8
When we implement the previous recursive algorithm in Java, the resulting method will have
first and last as parameters. Thus, its header will differ from the header of the iterative method
selectionSort given in Segment 8.6. We could, however, provide the following method to sim-
ply invoke the recursive method:
public static <T extends Comparable<? super T>>
void selectionSort(T[] a, int n)
{
selectionSort(a, 0, n - 1); // invoke recursive method
} // end selectionSort
Whether you make the recursive method selectionSort private or public is up to you, but making
it public provides the client with a choice of two ways in which to invoke the sort. In a similar fash-
ion, you could revise the iterative selection sort given in Segment 8.6 to use the parameters first
and last (see Exercise 6) and then provide the method just given to invoke it.
With these observations in mind, we will make the subsequent sorting algorithms more general
by giving them three parameters— a , first , and last —so that they sort the entries a[first]
through a[last] .
The Efficiency of Selection Sort
8.9
In the iterative method selectionSort , the for loop executes n - 1 times, so it invokes the methods
getIndexOfSmallest and swap n - 1 times each. In the n - 1 calls to getIndexOfSmallest , last is
n - 1 and first ranges from 0 to n - 2. Each time getIndexOfSmallest is invoked, its loop exe-
cutes last - first times. Thus, this loop executes a total of
( n - 1) + ( n - 2) + . . . + 1
times. This sum is n ( n - 1) / 2. Since the operations in the loop are O(1), the selection sort is O( n 2 ).
Notice that our discussion does not depend on the nature of the data in the array. It could be wildly
out of order, nearly sorted, or completely sorted; in any case, selection sort would be O( n 2 ).
The recursive selection sort performs the same operations as the iterative selection sort, and so
it is also O( n 2 ).
Note: The time efficiency of selection sort
Selection sort is O( n 2 ) regardless of the initial order of the entries in an array. Although the
sort requires O( n 2 ) comparisons, it performs only O( n ) swaps. Thus, the selection sort
requires little data movement.
 
 
Search WWH ::




Custom Search