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
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.