In this section we consider two sorting algorithms that are not comparison-based. These algorithms are specialized for sorting small integers. These algorithms get around the lower-bounds of Theorem 11.5 by using (parts of) the elements of as indices into an array. Consider a statement of the form
Suppose we have an input array consisting of integers, each in the range . The counting-sort algorithm sorts using an auxiliary array of counters. It outputs a sorted version of as an auxiliary array .
The idea behind counting-sort is simple: For each , count the number of occurrences of in and store this in . Now, after sorting, the output will look like occurrences of 0, followed by occurrences of 1, followed by occurrences of 2,..., followed by occurrences of . The code that does this is very slick, and its execution is illustrated in Figure 11.7:
int[] countingSort(int[] a, int k) { int c[] = new int[k]; for (int i = 0; i < a.length; i++) c[a[i]]++; for (int i = 1; i < k; i++) c[i] += c[i-1]; int b[] = new int[a.length]; for (int i = a.length-1; i >= 0; i--) b[--c[a[i]]] = a[i]; return b; }
The first loop in this code sets each counter so that it counts the number of occurrences of in . By using the values of as indices, these counters can all be computed in time with a single for loop. At this point, we could use to fill in the output array directly. However, this would not work if the elements of have associated data. Therefore we spend a little extra effort to copy the elements of into .
The next loop, which takes time, computes a running-sum of the counters so that becomes the number of elements in that are less than or equal to . In particular, for every , the output array, , will have
The counting-sort algorithm has the nice property of being stable; it preserves the relative order of elements that are equal. If two elements and have the same value, and then will appear before in . This will be useful in the next section.
Counting-sort is very efficient for sorting an array of integers when the length, , of the array is not much smaller than the maximum value, , that appears in the array. The radix-sort algorithm, which we now describe, uses several passes of counting-sort to allow for a much greater range of maximum values.
Radix-sort sorts -bit integers by using passes of counting-sort to sort these integers bits at a time.2 More precisely, radix sort first sorts the integers by their least significant bits, then their next significant bits, and so on until, in the last pass, the integers are sorted by their most significant bits.
int[] radixSort(int[] a) { int[] b = null; for (int p = 0; p < w/d; p++) { int c[] = new int[1<<d]; // the next three for loops implement counting-sort b = new int[a.length]; for (int i = 0; i < a.length; i++) c[(a[i] >> d*p)&((1<<d)-1)]++; for (int i = 1; i < 1<<d; i++) c[i] += c[i-1]; for (int i = a.length-1; i >= 0; i--) b[--c[(a[i] >> d*p)&((1<<d)-1)]] = a[i]; a = b; } return b; }(In this code, the expression extracts the integer whose binary representation is given by bits of .) An example of the steps of this algorithm is shown in Figure 11.8.
|
This remarkable algorithm sorts correctly because counting-sort is a stable sorting algorithm. If are two elements of and the most significant bit at which differs from has index , then will be placed before during pass and subsequent passes will not change the relative order of and .
Radix-sort performs passes of counting-sort. Each pass requires time. Therefore, the performance of radix-sort is given by the following theorem.
If we think, instead, of the elements of the array being in the range , and take we obtain the following version of Theorem 11.8.