Pigeonhole sort
|
|
Pigeonhole sorting takes linear time (O(n)), which is the best possible performance for a sort algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. However, pigeonhole sorting is only practical if the objects you are sorting fall within (or can be mapped into) a range of possible values that is small compared to the size of the list to be sorted.
The algorithm's efficiency is reduced whenever more than one non-equivalent item gets sorted into the same pigeonhole. (If you have to sort within each pigeonhole, you've defeated the purpose because you're now inspecting each item more than once.) So for simplicity, and to keep the "classic" pigeonhole sort distinct from its many variations, we specify that the mapping must be reversible, ie, if two items end up in the same bucket then they must have the same value. Multiple items with the same value in the same bucket are no problem, just put them into the sorted list adjacent to each other (this can even be implemented as a stable sort (see sorting)).
The pigeonhole algorithm works as follows.
- Set up an array of initially empty "pigeonholes", one pigeonhole for each value in the range of keys.
- Go over the original array, putting each object in its pigeonhole.
- Iterate over the pigeonhole array in order, and put elements from non-empty holes back into the original array.
The hidden constant for this algorithm depends critically on the density of the elements in the pigeonhole array. If there are many more array elements than items to be sorted, steps 1 and 3 will be relatively slow.
Pigeonhole sort is rarely used as the requirements are rarely met and other, more flexible, and almost as fast, sorting algorithms are easier to use. In particular, the bucket sort is a more practical variation on the pigeonhole sort. If you think about it, quicksort is also a generalized kind of pigeonhole sort (with just two pigeonholes at any time).
Sample C99 code for this algorithm:
void pigeonhole_sort(int *low, int *high, int min, int max)
{
/* used to keep track of the size of the list we're sorting */
int count;
/* pointer into the list we're sorting */
int *current;
/* size of range of values in the list (ie, number of pigeonholes we need)*/
const int size = max - min + 1;
/* our array of pigeonholes */
int holes[size];
/* make absolutely certain that the pigeonholes start out empty */
for (int i = 0; i < size; ++i)
holes[i] = 0;
/* Populate the pigeonholes. */
for (current = low; current <= high; current++)
holes[*current - min] += 1;
/* Put the elements back into the array in order. */
for (current = low, count = 0; count < size; count++)
while (holes[count]-- > 0)
*current++ = count + min;
}
Note that min and max could also easily be determined within the function.