This C Program implement pigeonhole sort. Pigeonhole sorting, also known as count sort, is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same.[1] It requires O(n + N) time

Here is source code of the C Program to implement pigeonhole sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C Program to Implement Pigeonhole Sort`

`*/`

`#include <stdio.h>`

`#define MAX 7`

void pigeonhole_sort(int, int, int *);

void main()

`{`

int a[MAX], i, min, max;

printf("enter the values into the matrix :");

for (i = 0; i < MAX; i++)

`{`

scanf("%d", &a[i]);

`}`

min = a[0];

max = a[0];

for (i = 1; i < MAX; i++)

`{`

if (a[i] < min)

`{`

min = a[i];

`}`

if (a[i] > max)

`{`

max = a[i];

`}`

`}`

pigeonhole_sort(min, max, a);

printf("Sorted order is :\n");

for (i = 0; i < MAX; i++)

`{`

printf("%d", a[i]);

`}`

`}`

`/* sorts the array using pigeonhole algorithm */`

void pigeonhole_sort(int mi, int ma, int * a)

`{`

int size, count = 0, i;

int *current;

current = a;

size = ma - mi + 1;

int holes[size];

for (i = 0; i < size; i++)

`{`

holes[i] = 0;

`}`

for (i = 0; i < size; i++, current++)

`{`

holes[*current-mi] += 1;

`}`

for (count = 0, current = &a[0]; count < size; count++)

`{`

while (holes[count]--> 0)

`{`

*current++ = count + mi;

`}`

`}`

`}`

$cc pigeonholesort.c /* average case */ $ a.out enter the values into the matrix :7 3 8 2 5 4 9 Sorted order is : 2345789 /* best case */ $ a.out enter the values into the matrix :1 2 3 4 5 6 7 Sorted order is : 1234567 /* worst case */ $ a.out enter the values into the matrix :7 6 5 4 3 2 1 Sorted order is : 1234567

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.