Java Reference
In-Depth Information
figure 8.11
The steps of quicksort
81
75
31
57
13
43
26
0
92
65
Select pivot
81
75
31
57
13
43
26
0
92
65
Partition
0
75
65
31
13
43
81
92
57
26
Quicksort
small items
Quicksort
large items
0
13
26
31
43
57
65
75
81
92
0
13
26
31
43
57
65
75
81
92
The pivot is not larger than the smallest element in the group of large
elements by virtue of the partition.
n
The group of large elements is sorted by virtue of the recursion.
n
Although the correctness of the algorithm is easily established, why it is
faster than mergesort is not clear. Like mergesort, it recursively solves two
subproblems and requires linear additional work (in the form of the partition-
ing step). Unlike mergesort, however, quicksort subproblems are not guaran-
teed to be of equal size, which is bad for performance. However, quicksort
Quicksort is fast
because the parti-
tioning step can be
performed quickly
and in place.
Search WWH ::
Custom Search