Java Reference
In-Depth Information
Display 12.8 Quick Sort Realization of Sorting Pattern (part 3 of 3)
51
return (begin + up);
52
}
53
private static void join( double [] a, int begin,
54
int splitPoint, int end)
55
{
56
//Nothing to do.
57
}
58
}
Restrictions on the Sorting Pattern
The sorting pattern, like all patterns, has some restrictions on where it applies. As we
formulated the sorting pattern, it applies only to types for which the < operator is
defined and it applies only to sorting into increasing order; it does not apply to sorting
into decreasing order. However, this is a result of our simplifying details to make the
presentation clearer. You can make the pattern more general by replacing the < opera-
tor with a boolean valued method called compare that has two arguments of the base
type of the array and that returns true or false depending on whether the first
“comes before” the second. Then, the only restriction is that the compare method must
have a reasonable definition. 1 This sort of generalization is discussed in Chapter 13 in
the subsection entitled “The Comparable Interface.”
Efficiency of the Sorting Pattern
Essentially any sorting algorithm can be realized using this sorting pattern. However,
the most efficient implementations are those for which the split method divides the
array into two substantial size chunks, such as half and half, or one-forth and three-
fourths. A realization of split that divides the array into one or a very few elements
and the rest of the array will not be very efficient.
For example, the merge sort realization of split divides the array into two roughly
equal parts, and merge sort is indeed very efficient. It can be shown (although we will
not do so here) that merge sort has a worst-case running time that is the best possible
“up to an order of magnitude.”
1 The technical requirement is that the compare method be a total ordering , a concept discussed in
Chapter 13. Essentially, all common orderings that you might want to sort by are total orderings.
The Comparable interface has a method compareTo , which is slightly different from compare .
However, the method we described as compare can easily be defined using the method compareTo
as a helping method.
 
Search WWH ::




Custom Search