Algorithms in a Nutshell

Analysis in the Best, Average, and Worst Cases | 19

AlgorithmsThe Math of

Although SORT-4 from Figure 2-2 was the slowest of the four algorithms for

sortingnrandom strings, it turns out to be the fastest when the data is already

sorted. This advantage rapidly fades away, however, with just 16 random items

out of position, as shown in Figure 2-3.

However, suppose an input array withnstrings is “nearly sorted”—that is,n/4 of

the strings (25% of them) are swapped with another position just four locations

away. It may come as a surprise to see in Figure 2-4 that SORT-4 outperforms the

others.

The conclusion to draw is that for many problems, no single optimal algorithm

exists. Choosing an algorithm depends on understanding the problem being

solved and the underlying probability distribution of the instances likely to be

treated, as well as the behavior of the algorithms being considered.

Figure 2-3. Comparing sort algorithms on sorted and nearly sorted data

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