Algorithms in a Nutshell

Counting Sort | 91

Sorting

Algorithms

Counting Sort

An accountant is responsible for reviewing the books for a small restaurant. Each

night when the restaurant closes, the owner records the total sales for the day and

prints a receipt showing the date and the total. These receipts are tossed into a

large box. At the end of the year, the accountant reviews the receipts in the box to

see whether any are missing. As you can imagine, the receipts in the box are in no

particular order.

The accountant could sort all receipts in ascending order by date and then review

the sorted collection. As an alternative, she could grab a blank calendar for the

year and, one by one, pull receipts from the box and mark those calendar days

with an X. Once the box is empty, the accountant need only review the calendar

to see the days that were not marked. Note that at no point in this second alterna-

tive are two receipts ever compared with each other. If the restaurant were open

for 60 years and the accountant had calendars for each year, this approach would

not be efficient if there were only five receipts in the box; however, it would be

efficient if 20,000 receipts were in the box. The density of possible elements that

actually appear in the data set determines the efficiency of this approach.

At the beginning of this chapter, we proved that no sorting algorithm can sortn

elements in better than O(nlogn) time if comparing elements. Surprisingly, there

are other ways of sorting elements if you know something about those elements in

advance. For example, assume that you are asked to sortnelements, but you are

told that each element is a value in the range [0,k), wherekis much smaller than

n. You can take advantage of the situation to produce a linear—O(n)—sorting

algorithm, known as COUNTINGSORT.

Context

COUNTINGSORT, as illustrated in Figure 4-17, does not require a comparison

function and is best used for sorting integers from a fixed range [0,k). It can also

be used whenever a total ordering ofkelements can be determined and a unique

integer 0≤i<kcan be assigned for thosekelements. For example, if sorting a set of

fractions of the form 1/p(wherepis an integer) whose maximum denominatorp

isk, then each fraction 1/p can be assigned the unique valuek–p.

Table 4-4. Performance comparison of non-recursive variation (in seconds)

n Non-recursive Heap Sort Recursive Heap Sort

16,384 0.0118 0.0112

32,768 0.0328 0.0323

65,536 0.0922 0.0945

131,072 0.2419 0.2508

262,144 0.5652 0.6117

524,288 1.0611 1.1413

1,048,576 2.0867 2.2669

2,097,152 4.9065 5.3249

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