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