Java Reference
In-Depth Information
Thus, to sort a segment of
16
elements, or
2
4
elements, takes at most 4*
2
4
array comparisons. We can generalize this: to sort a segment of
2
n
elements takes
at most
n*2
n
comparisons. However, this is only in the case that each call to
par-
tition
partitions the segment into two segments of roughly the same size. The
next section shows you a case where performance is not so good.
15.4.4
Quicksort at its worst
We do the same analysis for sorting an array that is already in ascending order:
Activity
15-4.3
0 15
0 1 1 2 2 3 4 5 5 6 6 7 7 8 8 9
Since the pivot value is
0
, the call to
partition
could yield this array:
j 15
0 1 1 2 2 3 4 5 5 6 6 7 7 8 8 9
This call to
partition
took at most
16
array comparisons because each element
of the array has to be looked at.
Sorting the empty segment
b[0..j-1]
takes no time. But sorting
b[j+1..
15]
requires partitioning the segment, which requires up to
15
array comparisons
and could produce the following:
j 15
1 1 2 2 3 4 5 5 6 6 7 7 8 8 9
We see that if the pivot value is the smallest value in an array segment of
size
n
, partitioning the array takes up to
n
array comparisons and may produce
an empty segment and a segment of size
n-1
. This means that to sort the 16-
element array could take up to:
16+15+14+...+1=17*16/2
array comparisons. Generalizing, to sort an array of size
n
could take up to
n*
(n + 1) / 2
array comparisons, which is as bad as
insertionsort
or
selec-
tionsort
.
Quicksort
does its worst on an array that is already sorted!
Further, the
depth of recursion in this worst case is the size of the array
, so
quicksort
may take space proportional to the size of the array, and that is bad.
We cannot easily reduce the worst-case time of
quicksort
, but we can take
a few steps to reduce the probability of it happening. We can also modify
quick-
sort
to reduce the worst-case space requirements by reducing to
n
the maximum
depth of recursion to sort an array of size
2
n
. We see these changes in the next
two subsections.
Search WWH ::
Custom Search