The algorithm works as follows.
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, sorting algorithms are easier to use.
Sample C code for this algorithm:
void pigeonhole_sort ( int *low , int *high , int minvalue , int maxvalue ) { /* minvalue and maxvalue can also easily be determined within this function */ int count , size = maxvalue - minvalue + 1 , *current ; bool holes[size] ; for ( count = 0 ; count < size ; count++ ) /*Initializing*/ holes[count] = false ; for ( current = low ; current <= high ; current++ ) /*Sorting*/ holes[(*current)-minvalue] = true ; for ( current = low , count = 0 ; count < size ; count++ ) { if ( holes[count] ) { *current = count + minvalue ; current++ ; } } }
Search Encyclopedia
|
Featured Article
|