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

Distribution Sorting

The final class of sorting algorithm considered in this chapter consists of algorithms that sort by distribution  . The unique characteristic of a distribution sorting algorithm is that it does not make use of comparisons to do the sorting.

Instead, distribution sorting algorithms rely on a priori knowledge about the universal set from which the elements to be sorted are drawn. For example, if we know a priori that the size of the universe is a small, fixed constant, say m, then we can use the bucket sorting algorithm described in Section gif.

Similarly, if we have a universe the elements of which can be represented with a small, finite number of bits (or even digits, letters, or symbols), then we can use the radix sorting algorithm given in Section gif.




next up previous contents index

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