Java Reference

In-Depth Information

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

Search WWH ::

Custom Search