Algorithms in a Nutshell

Median Sort | 71

Sorting

Algorithms

are all greater than or equal topivot. How has this made any progress in selecting

the median value? Note thatpis to the left of the calculated location where the

median will ultimately end up in the sorted list (identified as the blackened array

element labeled “median location”). Therefore, none of the elements to the left of

pcan be the median value! We only need to recursively invokepartition(this

time with a differentA[pivotIndex] on the right half,A[p+1,right]) until it returns

p=median location.

Note thatpartitioneffectively organizes the array into two distinct subarrays

without actually sorting the individual elements.partitionreturns the indexpof

the pivot, and this can be used to identify thekthelement recursively in

A[left,right] for any 1≤k≤right–left+1, as follows:

if k=p+1

The selected pivot element is thekthvalue (recall that array indices start

counting at 0, butk starts counting at 1).

if k<p+1

Thekth element ofA is thekth element ofA[left,p].

if k>p+1

Thekth element ofA is the (k–p)th element ofA[p+1,right].

In Figure 4-10, the goal is to locate the median value ofA, or in other words, the

k=8thlargest element. Since the invocation ofpartitionreturnsp=5, we next

recursively search for the second smallest element inA[p+1,right].

Such a definition lends itself to a recursive solution, but it can also be defined iter-

atively where a tail-recursive function instead can be implemented within a loop

(see the code repository for the example).selectKthis an average-case linear time

function that returns the location of thekthelement in arrayargiven a suitable

pivotIndex; its implementation is shown in Example 4-4.

Figure 4-10. partition(0, 15, 9) returns 5 and updates A accordingly

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