Implementation of Pigeonhole Sort in C++
In this blog, we’ll be talking about how to implement PigeonHole Sort in C++.
PigeonHole Sort
Pigeon Hole algorithm is a nice algorithm to use when the number of elements is of the same order as the amount of possible key values.
i.e for an array-like {3,2,1,10000} ,this algorithm is not a good fit.
Though for an array-like {5,2,6,3,1,7} this algorithm is a suitable fit.
We can compare this algorithm with real-life pigeon holes as well.PiegonHoles is a type of cabinet that was used in earlier post offices, where each cell represented a specific delivery route.
So just like those PigeonHoles are objectives are to:
- Make a cabinet with enough holes
- Distribute the objects to their respective holes
- Recollect the object back from the cabinet
Algorithm Working:
Let’s assume we have an array
A = {5,2,6,3,1,7}
So as we can see here all the numbers are between 0-10 so we create a new array of size ten which would be our cabinet.
Cabinet = new Array(10)
Now we assign each element to the correct cabinet block.
foreach (number in A) cabinet[number] = number
Finally, we recollect all the elements from the Cabinet.
foreach number in cabinet if(number != NULL) add number to sortedItems return sortedItems
Finally, we’ll get a sorted array
Here one more derivative method we can use is to subtract the number from the minimum element that we are going to use as the index.
HOW WILL THIS HELP?
Ex: Consider an array = {99,102,105,103}.Here all the elements are close to each other still the Cabinet size turns out to be 105.
Instead, if we use the index as number-min(input) then all index would be between 0-10.Thus the cabinet size reduces to 10.
CODED SOLUTION
#include <stdio.h> #include <limits.h> #include <stdlib.h> //A function to find what size the cabinet should be //i.e nothing but the max-min+1 element in the array int SizeOfCabinet(int A[],int n) { long int max = LONG_MIN; long int min = LONG_MAX; for(int i=0;i<n;i++) { if(max < A[i]) max = A[i]; if(min > A[i]) min = A[i]; } return max-min+1; } //A function to find what is the minimum elements in the input array int minOfArray(int A[],int n) { long int min = LONG_MAX; for(int i=0;i<n;i++) { if(min > A[i]) min = A[i]; } return min; } int* PigeonHoleSort(int A[],int n) { int size = SizeOfCabinet(A,n); int IndexDecrease = minOfArray(A,n); //Initialization of the Cabinet int* Cabinet = (int*) malloc(size * sizeof(int)); int* sortedItems = (int*) malloc(n * sizeof(int)); for(int i=0;i<size;i++) { Cabinet[i] = NULL; } //Distribution of the elements for(int i=0;i<n;i++) { Cabinet[A[i]-IndexDecrease] = A[i]; } //Recollection of the sorted elements int k=0; for(int i=0;i<size;i++) { if(Cabinet[i] != NULL) { sortedItems[k] = Cabinet[i]; k++; } } return sortedItems; } int main(void) { int arr[10] = {100,54,53,52,51,50,49,48,46,45}; int *p = PigeonHoleSort(arr,10); for(int i=0;i<10;i++) { printf("%d ",p[i]); } return 0; }
The time complexity of this algorithm is O(n+N).
n = Size of the input array
N = range of the possible key values of the input array.
OUTPUT:
45 46 48 49 50 51 52 53 54 100
Leave a Reply