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]
.
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.