Java Reference
In-Depth Information
The next smallest value is the 5 in a[4] . The sort then interchanges the value in a[4] with the
value in a[1] . So far, the values in a[0] and a[1] are the smallest in the array and are in their cor-
rect position within the final sorted array. The algorithm then interchanges the next smallest
entry—the 8—with a[2] , and so on until the entire array is sorted.
FIGURE 8-3
A selection sort of an array of integers into ascending order
a[0] a[1] a[2] a[3] a[4]
15
8
10
2
5
15
8
10
2
5
2
15
8
10
5
2
15
8
10
5
2
5
10
15
8
2
5
10
15
8
2
5
8
15
10
2
5
8
15
10
2
5
8
10
15
Iterative Selection Sort
8.5
The following pseudocode describes an iterative algorithm for the selection sort:
Algorithm selectionSort(a, n)
// Sorts the first n entries of an array a .
for (index = 0; index < n - 1; index++)
{
indexOfNextSmallest = the index of the smallest value among
a[index], a[index + 1], . . . , a[n - 1]
Interchange the values of a[index] and a[indexOfNextSmallest]
// Assertion: a[0] a[1] . . . a[index] , and these are the smallest
// of the original array entries. The remaining array entries begin at a[index + 1].
}
Notice that during the last iteration of the for loop, the value of index is n - 2 , even though the
last array entry is a[n - 1] . Once the entries a[0] through a[n - 2] are in their correct places, only
the one entry a[n - 1] remains to be positioned. But since the other entries are correctly positioned,
it must already be in the correct place as well.
 
 
Search WWH ::




Custom Search