Sorting algorithms - Data Structures and Problem Solving Using Java - page 367

8.6.1 the quicksort algorithm

The basic quick-
sort algorithm is
recursive. Details
include choosing
the pivot, deciding
how to partition,
and dealing with
duplicates. Wrong
decisions give qua-
dratic running times
for a variety of
common inputs.

The basic algorithm Quicksort ( S ) consists of the following four steps.

1. If the number of elements in S is 0 or 1, then return.

2. Pick any element v in S . It is called the pivot .

3. Partition S - { v } (the remaining elements in S ) into two disjoint

groups: L =

{ xSv ∈ - xv {} ≤ } and R = { xSv ∈ - {} xv ≥ } .

4. Return the result of Quicksort ( L ) followed by v followed by

Quicksort ( R ).

Several points stand out when we look at these steps. First, the multibase case
of the recursion includes the possibility that S might be an empty (multi) set. This
provision is needed because the recursive calls could generate empty subsets. Sec-
ond, the algorithm allows any element to be used as the pivot. The pivot divides
array elements into two groups: elements that are smaller than the pivot and ele-
ments that are larger than the pivot. The analysis performed here shows that some
choices for the pivot are better than others. Thus, when we provide an actual imple-
mentation, we do not use just any pivot. Instead we try to make an educated choice.

The pivot divides
array elements into
two groups: those
smaller than the
pivot and those
larger than the
pivot.

In the partition step, every element in S, except for the pivot, is placed in
either L (which stands for the left-hand part of the array) or R (which stands
for the right-hand part of the array). The intent is that elements that are
smaller than the pivot go to L and that elements larger than the pivot go to R .
The description in the algorithm, however, ambiguously describes what to do
with elements equal to the pivot. It allows each instance of a duplicate to go
into either subset, specifying only that it must go to one or the other. Part of a
good Java implementation is handling this case as efficiently as possible.
Again, the analysis allows us to make an informed decision.
Figure 8.11 shows the action of quicksort on a set of numbers. The pivot is
chosen (by chance) to be 65. The remaining elements in the set are partitioned
into two smaller subsets. Each group is then sorted recursively. Recall that, by
the third rule of recursion, we can assume that this step works. The sorted
arrangement of the entire group is then trivially obtained. In a Java implementa-
tion, the items would be stored in a part of an array delimited by low and high .
After the partitioning step, the pivot would wind up in some array cell p . The
recursive calls would then be on the parts from low to p-1 and then p+1 to high .
Because recursion allows us to take the giant leap of faith, the correctness
of the algorithm is guaranteed as follows.

In the partition step
every element
except the pivot is
placed in one of
two groups.

The group of small elements is sorted by virtue of the recursion.

n

The largest element in the group of small elements is not larger than
the pivot by virtue of the partition.

n