Implementation of Pigeonhole Sort in C++

By Saksham Agarwal

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