C program for Pigeonhole Sort Algorithm | C code champ

# C program for Pigeonhole Sort Algorithm | C code champ

3949
4
SHARE

C program for Pigeonhole sort algorithm : Pigeonhole sorting, also known as count sort (not to be confused with counting 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.

The pigeonhole algorithm works as follows:

1. Given an array of values to be sorted, set up an auxiliary array of initially empty “pigeonholes,” one pigeonhole for each key through the range of the original array.
2. Going over the original array, put each value into the pigeonhole corresponding to its key, such that each pigeonhole eventually contains a list of all values with that key.
3. Iterate over the pigeonhole array in order, and put elements from non-empty pigeonholes back into the original array.

Now let us see how to write a which accepts number of elements and their values from user and generates the output file using pigeon sort.

### C program for Pigeonhole Sort Algorithm :

```#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void pigeonhole_sort(int arr[], int num, int min, int max)
{
int size,i,j,k,count;
size = max - min + 1;
// array of pigeonholes
int holes[size];
for(i=0;i<size;i++)
{
holes[i]=0;
}
// Populate the pigeonholes.
for (j=0; j < num ;j++)
holes[arr[j] - min]++;

// Put the elements back into the array in order.
k=0;
for (count = 0; count < size; count++)
while (holes[count]-- > 0)
{
arr[k] = count + min;
k=k+1;
}
}

int main()
{
int i,n, array[100], c, d, t,min,max, flag=0;
printf("-----------------------------------------------------------\n");
printf("-----------------------------------------------------------\n\n");
printf("\t\tPIGEONHOLE SORT ALGORITHM\n\n\n\n");
printf("Enter the number of input : ");
scanf("%d",&n);
printf("Enter the smallest value in the list: ");
scanf("%d",&min);
printf("Enter the largest number in the list : ");
scanf("%d",&max);
printf("\n\nEnter the elements to be sorted :\n");
for ( i = 0; i < n; i++)
{
scanf("%d",&array[i]);
if(array[i]<min && array[i]>max)
{
printf("\nEntered Element : %d is out of range \n",array[i]);
getch();
return 0;
}
}
for(i=0;i<n;i++)
{
if(array[i]<min || array[i]>max)
{
printf("\nEntered Element : %d is out of range \n",array[i]);
flag=1;
}
}
if(flag==1)
{
printf("\nEnter the elements correctly within %d and %d range\n",min,max);
}

if(flag==0) {
pigeonhole_sort(array, n,min,max);
printf("\n\nSorted List by Pigeonhole Sort :\n");
for ( i = 0; i < n; i++)
{
printf("%d\t",array[i]);
}
}
getch();
return 0;
}```

We hope you all have enjoyed the of Pigeonhole sort algorithm. If you have any issues with above code, let us know in form of comments.