Algorithms in a Nutshell

Principle: Decompose the Problem into Smaller Problems | 315

Epilogue

If you are sorting data, there is no “one size fits all” approach that consistently

delivers the best performance. Table 11-1 summarizes the results of the sorting

algorithms presented in Chapter 4. Do you have a set of integers from a limited

range to be sorted? No sorting algorithm will be faster than COUNTINGSORT,

although it requires more storage than other sorting algorithms. Do you have a set

of complex data that is already mostly sorted? INSERTIONSORTwill typically

outperform any other approach. Does relative ordering of equal elements matter

to you? If so, then a stable sorting algorithm is needed. Are you sure that your

input data is drawn from a uniform distribution? You must investigate using

BUCKETSORTbecause of its ability to take advantage of this property to provide

exceptional sorting performance. You will be able to select the most appropriate

algorithm based upon your data as you become more familiar with the available

options.

Principle: Decompose the Problem into Smaller

Problems

When designing an efficient algorithm to solve a problem, it is helpful if the

problem can be decomposed into two (or more) smaller subproblems. It is no

mistake that QUICKSORTremains one of the most popular sorting algorithms.

Even with the well-documented special cases that cause problems, QUICKSORT

offers the best average-case for sorting large collections of information. Indeed,

the very concept of an O(nlogn) algorithm is based on the ability to (a) decom-

pose a problem of sizeninto two subproblems of aboutn/2 in size, and (b)

recombine the solution of the two subproblems into a solution for the original

problem. To properly produce an O(nlogn) algorithm, it must be possible for

both of these steps to execute in O(n) time.

QUICKSORTwas the first in-place sorting algorithm to demonstrate O(nlogn)

performance. It succeeds by the novel (almost counterintuitive) approach for

dividing the problem into two halves, each of which can be solved recursively by

applying QUICKSORT to the smaller subproblems.

Table 11-1. Chapter 4: Sorting algorithms

Algorithm Best Average Worst Concepts Page

INSERTIONSORT nn^2 n^2 Array 64

MEDIANSORT n lognn lognn^2 Array, Recursion, Divide and

Conquer

68

SELECTKTH nnn^2 Divide and Conquer

BLUM-FLOYD-PRATT-RIVEST-

TARJAN(BFPRT) Select Kth

nnnRecursion, Divide and

Conquer

QUICKSORT n lognn lognn^2 Array, Recursion, Divide and

Conquer

79

SELECTIONSORT n^2 n^2 n^2 Array, Greedy

HEAPSORT n lognn lognn logn Array, Recursion, Binary Heap 87

COUNTINGSORT nnnArray 92

BUCKETSORT nnnArray, Hash 94

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

Licensed by

Ming Yi