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. For example, assume that you are asked to sort *n* elements, but you are told that each element is a value in the range [0,*k*), where *k* is much smaller than *n*. You can take advantage of the situation to produce a linear—O(*n*)—sorting algorithm, known as Counting Sort.

**Context**

Counting Sort, 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 of *k* elements can be determined and a unique integer 0≤*i*<*k* can be assigned for those *k* elements. For example, if sorting a set of fractions of the form 1/*p* (where *p* is an integer) whose maximum denominator *p* is *k*, then each fraction 1/*p* can be assigned the unique value *k*-*p*.

**Forces**

Counting Sort succeeds only because the *k* values form a total ordering for the elements.

**Solution**

Counting Sort creates *k* buckets that store the number of times the *k*^{th} element was seen in the input array. Counting Sort then makes two passes over the input array. During the first pass, Counting Sort increments the count of the *k*^{th} bucket. In the second pass, Counting Sort overwrites the original array by processing the count values in the total ordering provided by *k* buckets. The Counting Sort implementation in Example 4-10 relies on the calling function to determine the proper value for *k*.

Example 4-10. Counting Sort implementation

/** Sort the n elements in ar, drawn from the values [0,k). */ int countingSort +(int *ar, int n, int k) { int i, idx = 0; int *B = calloc (k, sizeof (int)); for (i = 0; i < n; i++) { B[ar[i]]++; } for (i = 0; i < k; i++) { while (B[i]-- > 0) { ar[idx++] = i; } } free(B); }

**Analysis**

Counting Sort makes two passes over the entire array. The first processes each of the *n* elements in the input array. In the second pass, the inner `while`

loop is executed *B*[*i*] times for each of the 0≤*i*<*k* buckets; thus the statement `ar[idx++]`

executes exactly *n* times. Together, the key statements in the implementation execute a total of 2**n* times, resulting in a total performance of O(*n*).

Counting Sort can only be used in limited situations because of the constraints that the elements in the array being sorted are drawn from a limited set of *k* elements. We now discuss Bucket Sort, which relaxes the constraint that each element to be sorted maps to a single bucket.

Start Free Trial

No credit card required