Java Reference
In-Depth Information
In
Chapter 5
you were shown a simple sorting method called the Bubble sort. It was men-
tioned at the time that substantially better sorts exist. Here you will develop a version of
one of the best: the Quicksort. The Quicksort, invented and named by C.A.R. Hoare, is
the best general-purpose sorting algorithm currently available. The reason it could not be
shown in
Chapter 5
is that the best implementations of the Quicksort rely on recursion. The
version we will develop sorts a character array, but the logic can be adapted to sort any type
of object you like.
The Quicksort is built on the idea of partitions. The general procedure is to select a value,
called the
comparand
, and then to partition the array into two sections. All elements great-
er than or equal to the partition value are put on one side, and those less than the value are
put on the other. This process is then repeated for each remaining section until the array is
sorted. For example, given the array
fedacb
and using the value
d
as the comparand, the
first pass of the Quicksort would rearrange the array as follows:
Initial f e d a c b
Pass1 b c a d e f
This process is then repeated for each section—that is,
bca
and
def
. As you can see,
the process is essentially recursive in nature, and indeed, the cleanest implementation of
Quicksort is recursive.
You can select the comparand value in two ways. You can either choose it at random,
or you can select it by averaging a small set of values taken from the array. For optimal
sorting, you should select a value that is precisely in the middle of the range of values.
However, this is not easy to do for most sets of data. In the worst case, the value chosen is
at one extremity. Even in this case, however, Quicksort still performs correctly. The version
of Quicksort that we will develop selects the middle element of the array as the comparand.
1
. Create a file called
QSDemo.java
.
2
. First, create the
Quicksort
class shown here:
