[Home]Pigeonhole sort

HomePage | Recent Changes | Preferences

Difference (from prior major revision) (minor diff, author diff)

Changed: 3c3
* 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.)

Changed: 12c12,30
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++ ;
}
}
}

Pigeonhole sorting takes linear time, which is the best possible performance for a sort algorithm since one has to look at all of the objects to be sorted. However, it requires

The algorithm works as follows.

  1. Set up an array of initially empty "pigeonholes" the size of the range.
  2. Go over the original array, putting each object in its pigeonhole.
  3. 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 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++ ;
          }
       }
 }

HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited November 22, 2001 6:02 am by Seb (diff)
Search: