Algorithms in a Nutshell

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 alternative 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 sort n elements in better than O(n log n) time if comparing elements. Surprisingly, there are other ways of sorting elements if you know something about those elements in advance. ...