Java Reference
In-Depth Information
see how to modify the algorithm to take advantage of this. We show how to min-
imize the maximum number of frames needed. For this explanation, assume that
the number of elements,
k+1-h
, is a power of 2, say
k+1-h = 2
n
.
After partitioning, two segments are sorted. We change the body so that the
smaller
of the two subsegments is sorted first, as shown in Fig. 15.10. First, note
that the new version is correct because the same two recursive calls are execut-
ed. The order in which they are executed may differ, but the order does not mat-
ter. Second, in each of the two cases, the last call is tail-recursive, so no extra
frame is needed for it.
Consider the first call in each of the two cases. The segment being sorted is
the smaller of the two, so it has less than
2
n-1
elements. We use this fact to deter-
mine the maximum depth of recursion, assuming that tail-recursive calls do not
need their own frames. The first frame is for a call with a segment of size 2
n
. The
next frame is for a call with a segment of size at most 2
n-1
. The next frame is for
a call with a segment of size at most 2
n-2
. And so on. Thus, the frames for the
calls are for segments of size
2
n
,
2
n-1
,
2
n-2
, ...
2
3
(remember that segments of
size
2
3
or less are base cases).
/**
Sort
b[h..k] */
public static void
quicksort(
int
[] b,
int
h,
int
k) {
tailRecursionLoop:
while
(
true
) {
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);
h= j + 1;
continue
tailRecursionLoop;
}
else
{
quicksort(b, j + 1, k);
// quicksort(b, h, j - 1);
k= j - 1;
continue
tailRecursionLoop;
}
} // tailRecursionLoop
}
Figure 15.11:
Quicksort
with tail recursion removed
Search WWH ::
Custom Search