Java Reference
In-Depth Information
The quick sort realization of
split
divides the array into two portions that might
be almost equal or might be very different in size depending on the choice of a split-
ting value. Since in extremely unfortunate cases the split might be very uneven for
most cases, the worst-case running time for quick sort is not as fast as that of merge
sort. However, in practice, quick sort turns out to be a very good sorting algorithm
and usually preferable to merge sort.
Section sort, which we discussed in Chapter 5, divides the array into two pieces,
one with a single element and one with the rest of the array interval. (See Self-Test
Exercise 4.) Because of this uneven division, selection sort has a poor running time,
although it does have the virtue of simplicity.
TIP: Pragmatics and Patterns
You should not feel compelled to follow all the fine details of a pattern. Patterns are
guides, not requirements. For example, we did the quick sort implementation by
exactly following the pattern. We did this to have a clean example. In practice we
would have taken some liberties. Notice that, with quick sort, the
join
method does
nothing. In practice we would simply eliminate the calls to
join
. These calls incur
overhead and accomplish nothing. Other optimizations can also be done once the
general pattern of the algorithm is clear.
■
Pattern Formalism
There is a well-developed body of techniques for using patterns. We will not go into
the details here. The UML discussed in Section 12.1 is one formalism used to express
patterns. The place within the software design process of patterns and any specific for-
malisms for patterns is not yet clear. However, it is clear that the basic idea of patterns,
as well as certain pattern names, such as
Model-View-Controller,
have become standard
and useful tools for software design.
Self-Test Exercises
4. Give an implementation of the divide-and-conquer sorting pattern (Display 12.5) that
will realize the selection sort algorithm (Display 6.11) for an array with base type
double
.
5. Which of the following would give the fastest run time when an array is sorted
using the quick sort algorithm: a fully sorted array, an array of random values, or an
array sorted from largest to smallest (that is, sorted backward)? Assume all arrays are
of the same size and have the same base type.
