Java Reference

In-Depth Information

15.4.1

Algorithm partition

Algorithm
quicksort
rests heavily on algorithm
partition
, which is discussed

in detail in activity 8-5.5 of the
ProgramLive
CD. In learning
quicksort
, it is

important that you understand what
partition
does, if not how it does it. We

explain it with an example. Here is its specification:

Activity 8-5.5

discusses algo-

rithm partition.

A footnote tells

you how to get

it from the CD.

/** b[h..k]
has at least three elements. Let
x
be the value initially

in b[h]
. Permute
b[h..k]
and return the integer
j
satisfying
R
:

b[h..j-1] ≤ b[j] = x ≤ b[j+1..k] */

public static int
partition(
int
[] b,
int
h,
int
k)

Here is an example. Suppose
b[h..k]
contains:

h k

5 4 8 7 5 2

The value in
b[h]
is called the
pivot
value. The call
partition(b, h, k)

rearranges
b[h..k]
to put elements smaller than the pivot value to its left and

larger elements to its right. But the arrangement of the values in the two seg-

ments is not specified. Also, the placement of elements that are equal to the pivot

value is not specified. We say that the specification is
nondeterministi
because

different implementations can give different results and still satisfy the specifi-

cation. In this case, there are several possibilities for the final arrangement of the

array segment, two of which are shown here:

h j k

2 4 5 7 5 8

h j k

4 2 5 5 7 8

The value
j
of the index of the pivot element
b[j]
is returned.

The specification of this function is nondeterministic. Since we do not care

about the order of values in the two final segments
b[h..j-1]
and
b[j+1..k]
,

function partition can be written to take time proportional to the number of ele-

ments,
k+1-h
. It makes up to
k+1-h
array comparisons.

15.4.2

Basic quicksort

We turn to procedure
quicksort
:

Activity

15-4.1

/**
Sort
b[h..k] */

public static void
quicksort(
int
[] b,
int
h,
int
k)

We take as the base case an array segment with fewer than
10
elements. In

this case, the array segment is sorted using
insertionsort
. Experiments have

shown that this base case is efficient. Procedure
quicksort
is fast on large seg-

ments but relatively slow on small ones.

Consider the case of an array segment with at least
10
elements. Partitioning

Search WWH ::

Custom Search