3.7 QUICKSORT 91PivotPoint = PivotPoint + 1
Swap( list[ PivotPoint ], list[ index ] )
end if
end for
// move pivot value into correct place
Swap( list[ first ], list[ PivotPoint ] )
return PivotPoint
■ 3.7.1 Worst-Case Analysis
WhenPivotList is called with a list of N elements, it does N 1 compari-
sons as it compares the PivotValue with every other element in the list. Because
we have already said that quicksort is a divide and conquer algorithm, you
might assume that a best case would be when PivotList creates two parts
that are the same size and you would be correct. The worst case would then be
when the lists are of drastically different sizes. The largest difference in the size
of these two lists occurs if the PivotValue is smaller (or larger) than all of the
other values in the list. In that case, we wind up with one part that has no ele-
ments and the other that has N 1 elements. If the same thing happens each
time we apply this process, we would only remove one element (the Pivot-
Value) from the list at each recursive call. This means we would do the num-
ber of comparisons given by the following formula:
What original ordering of elements would cause this behavior? If each pass
chooses the first element, that element must be the smallest (or largest). A list
that is already sorted is one arrangement that would cause this worst case
behavior! In all of the other sort algorithms we have considered, the worst and
average cases have been about the same, but as we are about to see, this is not
true for quicksort.
■ 3.7.2 Average-Case Analysis
You will recall that when we looked at shellsort, we considered the number of
inversions that each comparison removed in our analysis. At that time, we
pointed out that bubble sort and insertion sort didn’t do well on average
because they both removed only one inversion for each comparison.
WN() ()i– 1
i=2N
∑NN()– 1
==---------------------- 2 -