Algorithms in a Nutshell

Median Sort | 67

Sorting

Algorithms

Table 4-1 contains direct comparisons between a naïve implementation of value-

based INSERTIONSORTand the implementation from Example 4-2. Here 10

random trials of sortingnelements were conducted, and the best and worst

results were discarded. This table shows the average of the remaining eight runs.

Note how the implementation improves by using a block memory move rather

than individual memory swapping. Still, as the array size doubles, the perfor-

mance time approximately quadruples, validating the O(n^2 ) behavior of

INSERTIONSORT. Even with the bulk move improvement, INSERTIONSORTstill

remains quadratic since the performance of INSERTIONSORTusing bulk moves is

a fixed multiplicative constant (nearly 1/7) of the naïve INSERTIONSORT. The

problem with INSERTIONSORTis that it belongs to a conservative class of algo-

rithms (calledlocal transposition sorts) in which each element moves only one

position at a time.

When INSERTIONSORToperates over pointer-based input, swapping elements is

more efficient; the compiler can even generate optimized code to minimize costly

memory accesses.

Median Sort

Divide and conquer, a common approach in computer science, solves a problem

by dividing it into two independent subproblems, each about half the size of the

original problem. Consider the MEDIANSORTalgorithm (Figure 4-8) that sorts an

arrayAofn≥1 elements by swapping the median elementA[me] with the middle

element ofA(lines 2–4), creating a left and right half of the array. MEDIANSORT

then swaps elements in the left half that are larger thanA[mid] with elements in

the right half that are smaller or equal toA[mid] (lines 5–8). This subdivides the

original array into two distinct subarrays of about half the size that each need to

be sorted. Then MEDIANSORTis recursively applied on each subarray (lines

9–10).

A full example of MEDIANSORTin action is shown in Figure 4-9, in which each

row corresponds to a recursive invocation of the algorithm. At each step, there are

twice as many problems to solve, but each problem size has been cut in about half.

Table 4-1. Insertion Sort bulk move versus Insertion Sort (in seconds)

n

Insertion Sort bulk

move (Bn)

Naïve Insertion

Sort (Sn) Ratio B 2 n/Bn Ratio S 2 n/Sn

1,024 0.0055 0.0258

2,048 0.0249 0.0965 4.5273 3.7403

4,096 0.0932 0.3845 3.7430 3.9845

8,192 0.3864 1.305 4.1459 3.3940

16,384 1.3582 3.4932 3.5150 2.6768

32,768 3.4676 12.062 2.5531 3.4530

65,536 15.5357 48.3826 4.4802 4.0112

131,072 106.2702 200.5416 6.8404 4.1449

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