Algorithm Implementation/Sorting/Pigeonhole sort

All the examples currently on this page seem to be implementations of counting sort and not pigeonhole sort. Pigeonhole sort, when sorting a complex data structure with a key, keeps track of all the elements on a certain key (because equal elements are still distinct); rather than just keep a count like counting sort (which is only applicable to simple value types).

C99

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.

Java

public static void pigeonhole_sort(int[] a)
{
    // size of range of values in the list (ie, number of pigeonholes we need)
    int min = a[0], max = a[0];
    for (int x : a) {
        min = Math.min(x, min);
        max = Math.max(x, max);
    }
    final int size = max - min + 1;
 
    // our array of pigeonholes
    int[] holes = new int[size];  
 
    // Populate the pigeonholes.
    for (int x : a)
        holes[x - min]++;
 
    // Put the elements back into the array in order.
    int i = 0;
    for (int count = 0; count < size; count++)
        while (holes[count]-- > 0)
            a[i++] = count + min;
}

PHP

function pigeon_sort($arr)
{
//search min and max
$min = $max = $arr[0];
foreach ($arr as $num)
{       if ($num < $min)
                $min = $num;
        if ($num > $max)
                $max = $num;
}
 
foreach ($arr as $num)
        $d[$num-$min]++;
 
for ($i = 0; $i <= $max - $min; $i++ )
        while ($d[$i + $min]-- > 0)$res[] = $i+$min;
return $res;
}

Python

def pigeonhole_sort(a):
    # size of range of values in the list (ie, number of pigeonholes we need)
    my_min = min(a)
    my_max = max(a)
    size = my_max - my_min + 1
 
    # our list of pigeonholes
    holes = [0] * size
 
    # Populate the pigeonholes.
    for x in a:
        assert type(x) is int, "integers only please"
        holes[x - my_min] += 1
 
    # Put the elements back into the array in order.
    i = 0
    for count in xrange(size):
        while holes[count] > 0:
            holes[count] -= 1
            a[i] = count + my_min
            i += 1