Java Reference
In-Depth Information
Display 12.8
Quick Sort Realization of Sorting Pattern
(part 2 of 3)
11
*/
12
public static void
sort(
double
[] a,
int
begin,
int
end)
13 {
14
if
((end — begin) >= 1)
15 {
16
int
splitPoint = split(a, begin, end);
17 sort(a, begin, splitPoint);
18 sort(a, splitPoint + 1, end);
19 join(a, begin, splitPoint, end);
20 }
//else sorting one (or fewer) elements so do nothing.
21 }
The method
sort
is identical to the version in the
pattern (Display 12.5) except that
Type
is replaced
with
double.
22
private static int
split(
double
[] a,
int
begin,
int
end)
23 {
24
double
[] temp;
25
int
size = (end — begin + 1);
26 temp =
new double
[size];
27
double
splitValue = a[begin];
28
int
up = 0;
29
int
down = size — 1;
30
//Note that a[begin]
=
splitValue is skipped.
31
for
(
int
i = begin + 1; i < = end; i++)
32 {
33
if
(a[i] <= splitValue)
34 {
35 temp[up] = a[i];
36 up++;
37 }
38
else
39 {
40 temp[down] = a[i];
41 down——;
42 }
43 }
44
//0
< =
up
=
down
<
size
45 temp[up] = a[begin];
//Positions the split value
46
//temp[i]
<=
splitValue for i
<
up
47
// temp[up]
=
splitValue
48
// temp[i]
>
splitValue for i
>
up
49
for
(
int
i = 0; i < size; i++)
