Algorithms in a Nutshell

Quicksort | 79

Sorting

Algorithms

In QUICKSORT, we no longer seek the median value, and instead select an

element according to some strategy (sometimes randomly, sometimes the left-

most, sometimes the middle one) to partition an array into subarrays. Thus

QUICKSORThas two steps, as shown in Figure 4-11. The array is partitioned

around apivotvalue, creating a left subarray that contains elements less than or

equal to thepivot, and a right subarray that contains elements greater than or

equal to thepivot. Each of these subarrays is then recursively sorted.

The random nature of the algorithm as described makes it a challenge to prove

that the average-case performance is still O(nlogn). We do not cover here the

advanced mathematical analytic tools needed to prove this result, but further

details on this topic are available in (Cormen et al., 2001).

Figure 4-11. Quicksort fact sheet

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