Programming and Problem Solving with Java

(^542) | Array-Based Lists

{

String temp; // Temporary variable

int passCount; // Loop control variable for outer loop

int searchIndex; // Loop control variable for inner loop

int minIndex; // Index of minimum so far

for (passCount = 0; passCount < numItems – 1; passCount++)

{

minIndex = passCount;

// Find the index of the smallest component

// in listItems[passCount]..listItems[numItems – 1]

for (searchIndex = passCount + 1; searchIndex < numItems; searchIndex++)

if (listItems[searchIndex].compareTo(listItems[minIndex]) < 0)

minIndex = searchIndex;

// Swap listItems[minIndex] and listItems[passCount]

temp = listItems[minIndex];

listItems[minIndex] = listItems[passCount];

listItems[passCount] = temp;

}

}

}

With each pass through the outer loop in selectSort, we look for the minimum value in

the rest of the array (listItems[passCount]through listItems[numItems – 1]). Therefore,

minIndexis initialized to passCountand the inner loop runs from searchIndexequal to passCount

+ 1through numItems – 1. Upon exit from the inner loop,minIndexcontains the position of the

smallest value. (Because the ifstatement is the only statement in the loop, we do not have

to enclose it in a block.)

This method may swap a component with itself, which occurs if no value in the re-

maining list is smaller than listItems[passCount]. We could avoid this unnecessary swap by

checking whether minIndexis equal to passCount. Because this comparison would occur in every

iteration of the outer loop, it is more efficient not to check for this possibility and just to

swap something with itself occasionally. For example, if our list contains 10,000 elements,

then making this comparison adds 10,000 operations to the execution of the loop, yet we

might save just a few dozen unnecessary swap operations as a result. Table 11.1 shows an

input file and the results of sorting the file.

This algorithm sorts the components into ascending order. To sort them into descend-

ing order, we must scan for the maximumvalue instead of the minimumvalue. Simply chang-

ing the test in the inner loop from “less than” to “greater than” accomplishes this goal. Of