Pigeonhole Sort Algorithm
The Pigeonhole Sort Algorithm is a sorting technique that is particularly effective when dealing with small ranges of integers or other data types with a well-defined, relatively small range of possible values. It is based on the principle that if a set of items can be distributed into a fixed number of categories or "pigeonholes," and if there are more items than pigeonholes, then at least one pigeonhole must contain more than one item. In the context of sorting, these pigeonholes represent the range of the input data, and the items are the individual elements to be sorted.
To perform Pigeonhole Sort, the algorithm first determines the range of the input data, which helps in defining the number of pigeonholes needed. Then, it creates an empty array of pigeonholes, with each pigeonhole initially set to hold zero items. The algorithm proceeds by iterating through the input data, placing each element into its corresponding pigeonhole based on its value. Once all the elements have been placed into their respective pigeonholes, the algorithm then iterates through the pigeonholes array, collecting the elements back into the original input array in sorted order. As a result, the Pigeonhole Sort Algorithm sorts the data in linear time, with a time complexity of O(n + range), where n is the number of elements and range is the size of the range of input data. However, this algorithm is not efficient for large ranges or non-integer data types, as it requires a substantial amount of additional memory for the pigeonholes.
#include <stdio.h>
#include <stdlib.h>
void pigeonholeSort(int arr[], int size)
{
int i, j, min = arr[0], max = arr[0], range;
// Getting range of the array using max and min
for (i=1; i<size; i++)
{
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
range = max - min + 1;
// Make 'holes' and put array's numbers in holes
int * holes = (int*)malloc(sizeof(int) * range);
for (i=0; i<range; i++)
{
holes[i] = 0;
}
for (i=0; i<size; i++)
{
holes[arr[i] - min]++;
}
// Copy the numbers back to the original array
j=0;
for (i=0; i<range; i++)
{
while (holes[i] > 0)
{
arr[j] = i + min;
holes[i]--;
j++;
}
}
free(holes);
}
int main()
{
int i, n;
printf("Enter the size of the array: ");
scanf("%d", &n);
int * arr = (int*)malloc(sizeof(int) * n);
for (i = 0; i < n; i++)
{
printf("Number #%d: ", i + 1);
scanf("%d", &arr[i]);
}
printf("You entered: ");
for (i=0; i<n; i++)
{
printf("%d ", arr[i]);
}
pigeonholeSort(arr, n);
printf("\nSorted array: ");
for (i=0; i<n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
free(arr);
return 0;
}
