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