Java Reference
In-Depth Information
I=0
1
2
3
4
5
6
42
20
17
13
28
14
23
15
13
20
17
42
28
14
23
15
13
14
17
42
28
20
23
15
13
14
15
42
28
20
23
17
13
14
15
17
28
20
23
42
13
14
15
17
20
28
23
42
13
14
15
17
20
23
28
42
13
14
15
17
20
23
28
42
Figure7.3
An example of Selection Sort. Each column shows the array after the
iteration with the indicated value of
i
in the outer
for
loop. Numbers above the
line in each column have been sorted and are in their final positions.
7.2.3
Selection Sort
Consider again the problem of sorting a pile of phone bills for the past year. An-
other intuitive approach might be to look through the pile until you find the bill for
January, and pull that out. Then look through the remaining pile until you find the
bill for February, and add that behind January. Proceed through the ever-shrinking
pile of bills to select the next one in order until you are done. This is the inspiration
for our last (n
2
) sort, called Selection Sort. The ith pass of Selection Sort “se-
lects” the ith smallest key in the array, placing that record into position i. In other
words, Selection Sort first finds the smallest key in an unsorted list, then the second
smallest, and so on. Its unique feature is that there are few record swaps. To find
the next smallest key value requires searching through the entire unsorted portion
of the array, but only one swap is required to put the record in place. Thus, the total
number of swaps required will be n1 (we get the last record in place “for free”).
Figure 7.3 illustrates Selection Sort. Below is a Java implementation.
static<EextendsComparable<?superE>>
voidSort(E[]A){
for(inti=0;i<A.length-1;i++){//Selecti'threcord
intlowindex=i; //Rememberitsindex
for(intj=A.length-1;j>i;j--)//Findtheleastvalue
if(A[j].compareTo(A[lowindex])<0)
lowindex=j; //Putitinplace
DSutil.swap(A,i,lowindex);
}
}
Selection Sort (as written here) is essentially a Bubble Sort, except that rather
than repeatedly swapping adjacent values to get the next smallest record into place,
we instead remember the position of the element to be selected and do one swap
at the end. Thus, the number of comparisons is still (n
2
), but the number of
swaps is much less than that required by bubble sort. Selection Sort is particularly
