Algorithm Implementation/Sorting/Pigeonhole sort
Appearance
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 | edit source]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 | edit source]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 | edit source]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 | edit source]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