SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 911

for (index = 0; index < listLength - 1; index++)
{

a. find the location, smallestIndex, of the smallest element in
list[index]...list[listLength].
b. Swap the smallest element with list[index]. That is, swap
list[smallestIndex] with list[index].

}

T efi t timet ht el , wel tet esm ll t lem t in
list[0]...list[listLength - 1] and swap this smallest element with list[0] .The
second time through the loop, we locate the smallest element in
list[1]...list[listLength-1] and swap this smallest element with list[1] ,andsoon.
Step a is similar to the algorithm of finding the index of the largest item in the list,
as discussed in Chapter 9. Here, we find the index of the smallest item in the list.
(See Programming Exercise 2 in Chapter 9.) The general form of step a is:

smallestIndex = index; //assume that the first element
//is the smallest

for (minIndex = index + 1; minIndex < listLength; minIndex++)
if (list[minIndex] < list[smallestIndex])
smallestIndex = minIndex; //current element in the list
//is smaller than the smallest so
//far, so update smallestIndex

Step b swaps the contents of list[smallestIndex] with list[index] . The following
statements accomplish this task:

temp = list[smallestIndex];
list[smallestIndex] = list[index];
list[index] = temp;
It follows that to swap these values, three item assignments are needed. The following
method, selectionSort , implements the selection sort algorithm:
public static void selectionSort( int [] list, int listLength)
{

int index;
int smallestIndex;
int minIndex;
int temp;

for (index = 0; index < listLength - 1; index++)
{

1
4

//Step a
smallestIndex = index;

for (minIndex = index + 1; minIndex < listLength;
minIndex++)
if (list[minIndex] < list[smallestIndex])
smallestIndex = minIndex;