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