Implementation

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

Implementation

Program introduces the BucketSorter class. The BucketSorter class extends the AbstractSorter class defined in Program . This bucker sorter is designed to sort specifically an array of ComparableInt32s. The BucketSorter class contains two fields, m and count. The integer m simply keeps track of the size of the universe. The count variable is an array of integers used to count the number of occurrences of each element of the universal set.

program45285
Program: BucketSorter class fields and constructor.

The constructor for the BucketSorter class takes a single argument which specifies the size of the universal set. The variable m is set to the specified value, and the count array is initialized to have the required size.

Program defines the no-arg Sort method. It begins by setting all of the counters to zero (lines 8-9). This can clearly be done in O(m) time.

program45299
Program: BucketSorter class Sort method.

Next, a single pass is made through the data to count the number of occurrences of each element of the universe (lines 10-11). Since each element of the array is examined exactly once, the running time is O(n).

In the final step, the sorted output sequence is created (lines 12-14). Since the output sequence contains exactly n items, the body of the inner loop (line 14) is executed exactly n times. During the iteration of the outer loop (line 12), the loop termination test of the inner loop (line 13) is evaluated times. As a result, the total running time of the final step is O(m+n).

Thus, the running time of the bucket sort method is O(m+n). Note that if m=O(n), the running time for bucket sort is O(n). That is, the bucket sort algorithm is a linear-time sorting algorithm! Bucket sort breaks the bound associated with sorting algorithms that use binary comparisons because bucket sort does not do any binary comparisons. The cost associated with breaking the running time bound is the O(m) space required for the array of counters. Consequently, bucket sort is practical only for small m. For example, to sort 16-bit integers using bucket sort requires the use of an array of counters.