Algorithms in a Nutshell

Quicksort | 81

Sorting

Algorithms

Context

QUICKSORTexhibits worst-case quadratic behavior if the partitioning at each

recursive step only divides a collection ofnelements into an “empty” and “large”

set, where one of these sets has no elements and the other hasn–1 (note that the

pivot element provides the last of then elements, so no element is lost).

The choice ofpivotstrongly influences the relative sizes of the two subarrays after

the execution ofpartition. Instead of just choosingpivotto be a random element,

one can choose it to be the median (middle value) ofkrandom elements for some

oddk. Later, in the “Variations” section, we discuss different strategies for

selecting thepivot.

Figure 4-13. A different Quicksort behavior

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