# 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