Algorithms in a Nutshell

57

Chapter 4. Sorting Algorithms......................................................................................................................................................

4

Sorting Algorithms

Overview

Given the list of states in Figure 4-1, how fast can you determine whether the state

“Wyoming” is in the list? Perhaps you can answer this question in less than a

second. How long would this task take in a list of 1,000 words? A good guess

would be 100 seconds, since the problem size has increased 100-fold. Now, given

the same list of states, can you determine the number of states whose names end

in the letters? This task is surprisingly easy because you can quickly see that the

states are sorted in increasing order by their last character. If the list contained

1,000 words ordered similarly, the task would likely require only a few additional

seconds because you can take advantage of the order of words in the list.

Numerous computations and tasks become simple by properly sorting informa-

tion in advance. The search for efficient sorting algorithms dominated the early

days of computing. Indeed, much of the early research in algorithms focused on

sorting collections of data that were too large for the computers of the day to store

in memory. Because computers are incredibly more powerful and faster than the

Figure 4-1. List of 10 states

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