Java Reference
In-Depth Information
static<EextendsComparable<?superE>>
voidqsort(E[]A,inti,intj){ //Quicksort
intpivotindex=findpivot(A,i,j);//Pickapivot
DSutil.swap(A,pivotindex,j); //Stickpivotatend
//kwillbethefirstpositionintherightsubarray
intk=partition(A,i-1,j,A[j]);
DSutil.swap(A,k,j); //Putpivotinplace
if((k-i)>1)qsort(A,i,k-1); //Sortleftpartition
if((j-k)>1)qsort(A,k+1,j); //Sortrightpartition
}
Figure7.11
Implementation for Quicksort.
placed at the end of the array (position
j
). Thus,
partition
must not affect the
value of array position
j
. After partitioning, the pivot value is placed in position
k
,
which is its correct position in the final, sorted array. By doing so, we guarantee
that at least one value (the pivot) will not be processed in the recursive calls to
qsort
. Even if a bad pivot is selected, yielding a completely empty partition to
one side of the pivot, the larger partition will contain at most n 1 elements.
Selecting a pivot can be done in many ways. The simplest is to use the first
key. However, if the input is sorted or reverse sorted, this will produce a poor
partitioning with all values to one side of the pivot. It is better to pick a value
at random, thereby reducing the chance of a bad input order affecting the sort.
Unfortunately, using a random number generator is relatively expensive, and we
can do nearly as well by selecting the middle position in the array. Here is a simple
findpivot
function:
static<EextendsComparable<?superE>>
intfindpivot(E[]A,inti,intj)
{return(i+j)/2;}
We now turn to function
partition
. If we knew in advance how many keys
are less than the pivot,
partition
could simply copy elements with key values
less than the pivot to the low end of the array, and elements with larger keys to
the high end. Because we do not know in advance how many keys are less than
the pivot, we use a clever algorithm that moves indices inwards from the ends of
the subarray, swapping values as necessary until the two indices meet. Figure 7.12
shows a Java implementation for the partition step.
Figure 7.13 illustrates
partition
. Initially, variables
l
and
r
are immedi-
ately outside the actual bounds of the subarray being partitioned. Each pass through
the outer
do
loop moves the counters
l
and
r
inwards, until eventually they meet.
Note that at each iteration of the inner
while
loops, the bounds are moved prior
to checking against the pivot value. This ensures that progress is made by each
while
loop, even when the two values swapped on the last iteration of the
do
loop were equal to the pivot. Also note the check that
r>l
in the second
while
loop. This ensures that
r
does not run off the low end of the partition in the case
