Java Reference
In-Depth Information
Display 13.5
Sorting Method for Array of
Comparable
(part 1 of 2)
1
public class
GeneralizedSelectionSort
2 {
3
/**
4
Precondition: numberUsed
<=
a.length;
5
The first numberUsed indexed variables have values.
6
Action: Sorts a so that a[0], a[1], ... , a[numberUsed
-
1] are in
7
increasing order by the compareTo method.
8
*/
9
public static void
sort(Comparable[] a,
int
numberUsed)
10 {
11
int
index, indexOfNextSmallest;
12
for
(index = 0; index < numberUsed - 1; index++)
13 {
//Place the correct value in a[index]:
14 indexOfNextSmallest = indexOfSmallest(index, a,
numberUsed);
15 interchange(index,indexOfNextSmallest, a);
16
//a[0], a[1],..., a[index] are correctly ordered and
//these are
17
//the smallest of the original array elements. The remaining
18
//positions contain the rest of the original array elements.
19 }
20 }
21
/**
22
Returns the index of the smallest value among
23
a[startIndex], a[startIndex
+
1], ... a[numberUsed
-
1]
24
*/
25
private static int
indexOfSmallest(
int
startIndex,
26
Comparable
[] a,
int
numberUsed)
27 {
28 Comparable min = a[startIndex];
29
int
indexOfMin = startIndex;
30
int
index;
31
for
(index = startIndex + 1; index < numberUsed; index++)
32
if
(a[index].compareTo(min) < 0)
//if a[index] is less than min
33 {
34 min = a[index];
35 indexOfMin = index;
36
//min is smallest of a[startIndex] through a[index]
37 }
38
return
indexOfMin;
39 }
(continued)
