|
|
|
|
|
|
|
int placeCount; // Loop control variable
int minIndex; // Index of minimum so far
for (passCount = 0; passCount < length - 1; passCount++)
{
// Invariant (prior to test):
// list[0..passCount-1] are in ascending order
// and contain the passCount smallest items
// && 0 <= passCount <= length - 1
minIndex = passCount;
// Find the index of the smallest component
// in list[passCount..length-1]
for (placeCount = passCount + 1; placeCount < length;
placeCount++)
// Invariant (prior to test):
// list[minIndex] <= all list[passCount..placeCount-1]
// && placeCount <= length
if (list[placeCount] < list[minIndex])
minIndex = placeCount;
// Swap list[minIndex] and list[passCount]
temp = list[minIndex];
list[minIndex] = list[passCount];
list[passCount] = temp;
}
} |
|
|
|
|
|
|
|
|
Note that with each pass through the inner loop, we are looking for the minimum value in the rest of the list (list[passCount] through list[length-1]). Therefore, minIndex is initialized to passCount and the inner loop runs from placeCount equal to passCount+1 through length-1. |
|
|
|
|
|
|
|
|
Note also that we may swap a component with itself, which occurs if no value in the remaining list is smaller than list[passCount]. We could avoid such an unnecessary swap by checking to see if minIndex is equal to passCount. Because this comparison would have to be made during each iteration of the loop, it is more efficient not to check for this possibility and just to swap something with itself occasionally. If the components we are sorting are much more complex than simple numbers, we might reconsider this decision. |
|
|
|
|
|
|
|
|
This algorithm sorts the components into ascending order. To sort them into descending order, we need to scan for the maximum value instead of |
|
|
|
|
|