Algorithm Implementation/Sorting/Pigeonhole sort

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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[edit]

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[edit]

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[edit]

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