Java Reference
In-Depth Information
Note:
Notation
In mathematics, one-letter variable names are common. Recognizing this, and seeking to
save some space, we use
a
and
n
within the text and pseudocode to represent, respectively, an
array and its number of entries. Within Java code elsewhere, we have tried to avoid one-letter
identifiers, using them only sparingly. However, the code that you will see in this chapter and
the next uses
a
and
n
simply to maintain consistency with the text.
8.6
The class in Listing 8-1 contains the public method
selectionSort
and two private methods that
assist in sorting. We can add other sorting methods as we develop them.
It is easy to see that the definition of
selectionSort
is a direct translation of the previous
pseudocode into Java code. The method
getIndexOfSmallest
searches the array entries
a[first]
through
a[last]
and returns the index of the smallest among them. The method uses two local vari-
ables,
min
and
indexOfMin
. At any point in the search,
min
references the smallest value found so far.
That value occurs at
a[indexOfMin]
. At the end of the search, the method returns
indexOfMin
.
Notice that for our purposes here, we could have assumed that
last
is always
n
-
1
and omitted it as a
parameter. However, this general version will be useful in other settings.
Since exchanging entries in an array does not involve the method
compareTo
, the method
swap
can simply use
Object
as the type of these entries.
LISTING 8-1
A class for sorting an array using selection sort
/**
Class for sorting an array of Comparable objects from smallest to
largest.
*/
public class
SortArray
{
/** Sorts the first n objects in an array into ascending order.
@param a an array of Comparable objects
@param n an integer > 0 */
public static
<T
extends
Comparable<?
super
T>>
void
selectionSort(T[] a,
int
n)
{
for
(
int
index = 0; index < n - 1; index++)
{
int
indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
// Assertion: a[0] <= a[1] <= . . . <= a[index] <= all other
// a[i]
}
// end for
}
// end selectionSort
/** Finds the index of the smallest value in a portion of an array.
@param a
an array of Comparable objects