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
 
Search WWH ::




Custom Search