Java Reference
In-Depth Information
72
6
57
88
60
42
83
73
48
85
Pivot = 60
48
6
57
42
60
88
83
73
72
85
Pivot = 6
Pivot = 73
6
42
57
48
72
73
85
88
83
Pivot = 57
Pivot = 88
57
85
83
88
Pivot = 42
42
48
Pivot = 85
42
48
83
85
6
42
48
57
60
72
73
83
85
88
Final Sorted Array
Figure7.14
An illustration of Quicksort.
how much work is done by the nested
while
loops. The
do
loop as a whole is
guaranteed to move both
l
and
r
inward at least one position on each first pass.
Each
while
loop moves its variable at least once (except in the special case where
r
is at the left edge of the array, but this can happen only once). Thus, we see that
the
do
loop can be executed at most s times, the total amount of work done moving
l
and
r
is s, and each
while
loop can fail its test at most s times. The total work
for the entire
partition
function is therefore (s).
Knowing the cost of
findpivot
and
partition
, we can determine the
cost of Quicksort. We begin with a worst-case analysis. The worst case will occur
when the pivot does a poor job of breaking the array, that is, when there are no
elements in one partition, and n 1 elements in the other. In this case, the divide
and conquer strategy has done a poor job of dividing, so the conquer phase will
work on a subproblem only one less than the size of the original problem. If this
happens at each partition step, then the total cost of the algorithm will be
n
X
k = (n
2
):
k=1
In the worst case, Quicksort is (n
2
). This is terrible, no better than Bubble
Sort.
2
When will this worst case occur? Only when each pivot yields a bad parti-
tioning of the array. If the pivot values are selected at random, then this is extremely
unlikely to happen. When selecting the middle position of the current subarray, it
2
The worst insult that I can think of for a sorting algorithm.
