Recursion - Multimedia Introduction to Programming Using Java - page 416

15.4.5 Quicksort's time/space problems

Making partition's segments closer in size
If the pivot value —the value in b[h] — is close to the smallest or largest
value in the array segment, function partition will produce two segments of
disparate sizes. We want the segments to be as close to the same size as possible.
Making them the same size would require finding the median of b[h..k] and
placing it in b[h] . However, finding the median takes so much time that the
algorithm in total would be less efficient. So we don't do that.
Instead, we look at three values, b[h] , b[(h + k) / 2] , and b[k] , and place
their median in b[h] . While this doesn't guarantee that the segments are closer
in size, it increases the chances that they will be. In activity 8-5.6 of Program-
Live , we develop a procedure medianOf3(b, h, k) to swap these three array ele-
ments to place the median in b[h] , and we call this procedure before calling
function partition (see Fig. 15.10).

Solving the space inefficiency
In Sec. 15.4.4, we saw that the space required by quicksort was propor-
tional to the maximum depth of recursion. The only way to reduce the space is
to reduce the number of frames that are placed on the stack. We know how to do
this in some cases, for we know how to implement tail-recursive calls without
using more frames.
In the basic quicksort of Fig. 15.8, the last call is indeed tail recursive. We

Activity
15-4.4

/** Sort b[h..k] */
public static void quicksort( int [] b, int h, int k) {
if (k+1-h < 10) {
insertionsort(b, h, k);
return ;

}

medianOf3(b, h, k);
// { b[h] is between b[(j +k/2)] and b[k] }
int j= partition(b,h,k);
// { b[h..j-1] <= b[j] <= b[j+1..k] }

if (j - h) <= k - j) {
quicksort(b, h, j - 1);
quicksort(b, j + 1, k);
} else {
quicksort(b, j + 1, k);
quicksort(b, h, j - 1);

}

}

Figure 15.10: Enhanced quicksort