Data Structures and Algorithms with Object-Oriented Design Patterns in C++

### Implementation

Program  gives the declaration of the RadixSorter class. Notice that the RadixSorter class is not a template. This radix sorter is designed to sort specifically an array of unsigned ints.

Three constants are declared as static members of the in the RadixSorter class--R, r and p. The constant R represents the radix and . The constant p is the number sorting passes needed to sort the data.

The RadixSorter class contains one member variable--count. The count variable is an array of unsigned integers used to implement the sorting passes. The RadixSorter constructor simply initializes the count array with length R.

Program: RadixSorter Class Definition

Program  defines the constants R, r and p, and gives the code for the DoSort member function of the RadixSorter class. In this case r=8 and . Therefore, a radix-256 sort is being done. We have chosen R as a power of two because that way the computations required to implement the radix sort can be implemented efficiently using simple bit shift and mask operations. In order to sort b-bit unsigned integers, it is necessary to make sorting passes. The constants r, R and p are initialized accordingly.

Program: RadixSorter Class DoSort Member Function Definition

DoSort begins by creating a temporary array of unsigned ints of length n. Each iteration of the main loop corresponds to one pass of the radix sort (lines 9-30). In all p iterations are required.

During the pass of the main loop the following steps are done: First, the R counters are all set to zero (lines 11-12). This takes O(R) time. Then a pass is made through the input array during which the number of occurrences of each radix-R digit in the digit position are counted (lines 13-17). This pass takes O(n) time. Notice that during this pass all the input data is copied into the temporary array.

Next, the array of counts is transformed into an array of offsets according to Equation . This requires a single pass through the counter array (lines 18-24). Therefore, it takes O(R) time. Finally, the data sequence is permuted by copying the values from the temporary array back into the input array (lines 25-30). Since this requires a single pass through the data arrays, the running time is O(n).

After the p sorting passes have been done, the array of data is sorted. The running time for the DoSort routine of the RadixSorter class is . If we assume that the size of an integer is 32 bits and given that R=256, the number of sorting passes required is p=4. Therefore, the running time for the radix sort is simply O(n). I.e., radix sort is a linear-time sorting algorithm.