Algorithms in a Nutshell

Median Sort | 73

Sorting

Algorithms

Consequences

MEDIANSORTdoes more work than it should. Although the generated subprob-

lems are optimal (since they are both about half the size of the original problem),

the extra cost in producing these subproblems adds up. As we will see in the

upcoming section on “Quicksort,” it is sufficient to selectpivotIndexrandomly,

which should avoid degenerate cases (which might happen if the original array is

already mostly sorted).

Analysis

MEDIANSORTguarantees that the recursive subproblems being solved are nearly

identical in size. This means the average-case performance of MEDIANSORTis

O(nlogn). However, in the worst case, thepartitionfunction executes in O(n^2 ),

which would force MEDIANSORTto degrade to O(n^2 ). Thus, even though the

subproblems being recursively sorted are ideal, the overall performance suffers

when consideringnitems already in sorted order. We ran MEDIANSORTusing a

randomizedselectPivotIndexfunction against this worst-case example where

selectPivotIndexalways returned the leftmost index. Ten trials were run, and the

best and worst results were discarded; the averages of the remaining eight runs for

these two variations are shown in the first two columns of Table 4-2. Observe that

in the worst case, as the problem size doubles, the time to complete MEDIAN

SORTmultiplies more than fourfold, the classic indicator for O(n^2 ) quadratic

performance.

void mediansort (void **ar, int(*cmp)(const void *,const void *),

int left, int right) {

/* if the subarray to be sorted has 1 (or fewer!) elements, done. */

if (right <= left) { return; }

/* get midpoint and median element position (1<=k<=right-left-1). */

int mid = (right - left + 1)/2;

int me = selectKth (ar, cmp, mid+1, left, right);

mediansort (ar, cmp, left, left+mid-1);

mediansort (ar, cmp, left+mid+1, right);

}

Table 4-2. Performance (in seconds) of Median Sort in the worst case

n

Randomized

pivot selection

Leftmost

pivot selection

Blum-Floyd-Pratt-Rivest-Tarjan

pivot selection

256 0.000088 0.000444 0.00017

512 0.000213 0.0024 0.000436

1,024 0.000543 0.0105 0.0011

2,048 0.0012 0.0414 0.0029

4,096 0.0032 0.19 0.0072

8,192 0.0065 0.716 0.0156

16,384 0.0069 1.882 0.0354

Example 4-5. Median Sort implementation in C (continued)

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