[Home]History of Pigeonhole sort

HomePage | Recent Changes | Preferences

Revision 6 . . (edit) November 22, 2001 6:02 am by Seb
Revision 5 . . (edit) November 22, 2001 6:00 am by Seb
Revision 4 . . (edit) November 22, 2001 6:00 am by Seb
Revision 3 . . November 22, 2001 3:14 am by Magnus Manske [Someone please check my C-code (I've been doing too much PHP lately...)]
Revision 2 . . (edit) November 22, 2001 12:42 am by Seb
Revision 1 . . November 22, 2001 12:41 am by Seb [Initial]
  

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++ ;
}
}
}

HomePage | Recent Changes | Preferences
Search: