Recursion - Multimedia Introduction to Programming Using Java - page 412

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