Algorithms in a Nutshell

(^80) | Chapter 4: Sorting Algorithms
Figure 4-12 shows QUICKSORTin action. Each of the black squares in the figure
represents a pivot selection in line 1 ofpartition. The first pivot selected is “2”,
which turns out to be a poor choice since it produces two subarrays of size 1 and
size 14. During the next recursive invocation of QUICKSORTon the right
subarray, “12” is selected to be the pivot, which produces two subarrays of size 9
and 4, respectively. Already you can see the benefit of usingpartitionsince the
last four elements in the array are, in fact, the largest four elements. Because of the
random nature of the pivot selection, different behaviors are possible. In a different
execution, shown in Figure 4-13, the first selected pivot nicely subdivides the
problem into two more-or-less comparable tasks.
Figure 4-12. Sample Quicksort execution
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use