Algorithms in a Nutshell

Median Sort | 69

Sorting

Algorithms

Context

Implementing MEDIANSORTdepends on efficiently selecting the median element

from an unsorted array. As is typical in computer science, instead of answering

this question, we answer a different question, which ultimately provides us with a

solution to our original question. Imagine someone provided you with a function

p=partition (left, right, pivotIndex), which selects the elementA[pivotIndex]

to be a specialpivotvalue that partitionsA[left,right] into a first half whose

elements are smaller or equal topivotand a second half whose elements are larger

or equal topivot. Note thatleft≤pivotIndex≤right, and the valuepreturned is the

location within the subarrayA[left,right] wherepivotis ultimately stored. A C

implementation ofpartition is shown in Example 4-3.

Figure 4-9. Median Sort in action on small array

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