Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Bucket Sort

 

Bucket sort is possibly the simplest distribution sorting algorithm. The essential requirement is that the size of the universe from which the elements to be sorted are drawn is a small, fixed constant, say m.

For example, suppose that we are sorting elements drawn from tex2html_wrap_inline69562, i.e., the set of integers in the interval [0,m-1]. Bucket sort uses m counters. The tex2html_wrap_inline57621 counter keeps track of the number of occurrences of the tex2html_wrap_inline57621 element of the universe. Figure gif illustrates how this is done.

   figure44911
Figure: Bucket sorting.

In Figure gif, the universal set is assumed to be tex2html_wrap_inline69572. Therefore, ten counters are required--one to keep track of the number of zeroes, one to keep track of the number of ones, and so on. A single pass through the data suffices to count all of the elements. Once the counts have been determined, the sorted sequence is easily obtained. For example, the sorted sequence contains no zeroes, two ones, one two, and so on.




next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.