Java Reference
In-Depth Information
Display 12.5
Divide-and-Conquer Sorting Pattern
1
/**
2
Precondition: Interval a[begin] through a[end] of a have elements.
3
Postcondition: The values in the interval have
4
been rearranged so that a[begin]
<=
a[begin
+
1]
<=
. . .
<=
a[end].
5*/
6
public static void
sort(
Type
[] a,
int
begin,
int
end)
7 {
8
if
((end - begin) >= 1)
9 {
10
int
splitPoint = split(a, begin, end);
11 sort(a, begin, splitPoint);
12 sort(a, splitPoint + 1, end);
13 join(a, begin, splitPoint, end);
14 }//
else sorting one (or fewer) elements so do nothing.
15 }
To get a correct Java method
definition,
Type
must be replaced
with a suitable type name.
Different definitions for the methods
split
and
join
will give different
realizations of this pattern.
EXAMPLE:
(continued)
The simplest realization of this sorting pattern is the
merge sort
realization given in
Display 12.6. In this realization, the array base type,
Type
, is specialized to the type
double
. The merge sort is an example where the definition of
split
is very simple.
It just divides the array into two intervals with no rearranging of elements. The
join
method is more complicated. After the two subintervals are sorted, the method
join
merges the two sorted subintervals, copying elements from the array to a temporary
array. The merging starts by comparing the smallest elements in each smaller sorted
interval. The smaller of these two elements is the smallest of all the elements in either
subinterval, so it is moved to the first position in the temporary array. The process
is then repeated with the remaining elements in the two smaller sorted intervals to
find the next smallest element, and so forth. A demonstration of using the merge sort
version of
sort
is given in Display 12.7 .
There is a trade-off between the complexity of the methods
split
and
join
. You
can make either of them simple at the expense of making the other more complicated.
For merge sort,
split
was simple and
join
was complicated. We next give a realization
where
split
is complicated and
join
is simple.
Display 12.8 gives the
quick sort
realization of our sorting pattern for the
type
double
.
In the quick sort realization, the definition of
split
is quite sophisticated. An
arbitrary value in the array is chosen; this value is called the
splitting value
. In our
realization, we chose
a[begin]
as the splitting value, but any value will do equally well.
The elements in the array are rearranged so that all those elements that are less than or
equal to the splitting value are at the front of the array, all the values that are greater
