Implementation

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Implementation

Program introduces the BucketSorter class. The BucketSorter class extends the abstract Sorter class defined in Program . This bucker sorter is designed to sort specifically an array ints. The BucketSorter class contains two instance attributes, _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.

program45380
Program: BucketSorter class __init__ method.

In addition to self, the __init__ method 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 _sort method. It begins by setting all of the counters to zero (lines 4-5). This can clearly be done in O(m) time.

program45397
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 6-7). 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 8-13). Since the output sequence contains exactly n items, the body of the inner loop (lines 10-13) is executed exactly n times. During the iteration of the outer loop (lines 9-13), the loop termination test of the inner loop (line 10) 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.