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.
−
1] are in
6
Action: Sorts a so that a[0], a[1], ... , a[numberUsed
7
increasing order by the compareTo method.
8
*/
9
public static void
sort(Comparable[] a,
int
numberUsed)
10
{
11
int
index, indexOfNextSmallest;
for
(index = 0; index < numberUsed
−
1; index++)
12
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
−
1]
23
a[startIndex], a[startIndex+1], ... a[numberUsed
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)
