Java Reference
In-Depth Information
the segment using partition(b, h, k) produces an array segment that looks
like this:
h j k
≤ b[j] ≥ b[j]
In this situation, what remains to be done? Well, segment b[h.. j -1] has to be
sorted and segment b[j+1..k] has to be sorted. Once they are in non-descend-
ing order, the complete segment b[h..k] is in non-descending order. So that is
it! The complete basic quicksort is given in Fig. 15.8.
15.4.3
Quicksort at its best
Figure 15.9 contains procedure quicksort with one change. The base case
occurs when the segment to be sorted has less than 2 elements, rather than 10 , so
that we can analyze quicksort on a small, 16-element array segment:
Activity
15-4.2
/** Sort b[h..k] */
public static void quicksort( int [] b, int h, int k) {
if (k+1-h < 10) {
insertionsort(b, h, k);
return ;
}
int j= partition(b, h, k);
// { b[h..j-1] <= b[j] <= b[j+1..k] }
quicksort(b, h, j - 1);
quicksort(b, j + 1, k);
}
Figure 15.8:
Basic quicksort
/** Sort b[h..k] */
public static void quicksort( int [] b, int h, int k) {
if (k+1-h<2) {
insertionsort(b, h, k);
return ;
}
int j= partition(b, h, k);
// { b[h..j-1] <= b[j] <= b[j+1..k] }
quicksort(b, h, j - 1);
quicksort(b, j + 1, k);
}
Figure 15.9:
Basic quicksort with a base case of a segment with at most one element
Search WWH ::

Custom Search