* an invertible function mapping the objects you are sorting to integers within a fixed range (say, 0 to 1000). (If you're sorting integers, just take them as they come.) |
* an invertible function mapping the objects you are sorting to integers within a fixed range (say, 0 to 1000). If an object precedes another, it must map to a smaller number. (If you're sorting integers, just take them as they come.) |
someone provide (pseudo)code? |
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++ ; } } } |
The algorithm works as follows.
The hidden constant for this algorithm depends critically on the size of the pigeonhole array. If it is too big, steps 1 and 3 will significantly slow down the algorithm.
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++ ; } } }