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
To get a correct Java method
definition
Type
must be replaced with
a suitable type name.
if
((end
−
begin) >= 1)
9
{
10
int
splitPoint = split(a, begin, end);
11
sort(a, begin, splitPoint);
Different definitions for the methods
split
and
join
will give different
realizations of this pattern.
12
sort(a, splitPoint + 1, end);
13
join(a, begin, splitPoint, end);
14
}
//else sorting one (or fewer) elements so do nothing.
15
}
EXAMPLE:
(continued)
The simplest realization of this sorting pattern is the
merge sort
realization given in Dis-
play 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 simply divides the
array into two intervals with no rearranging of elements. The
join
method is more compli-
cated. After the two subintervals are sorted, the method
join
merges the two sorted subinter-
vals, 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 and 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 arbi-
trary value in the array is chosen; this value is called the
splitting value
. In our realiza-
tion, 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 than the
