Pigeonhole is a sorting algorithm. It works best if the number of elements in the array and the number of keys is similar. It is a non-comparison sorting technique. For solving this algorithm, we must make some “holes” where we can store values. The number of holes is decided by the range of values. We will store there the temporary values associated with the index, and in the end, we move the values in the final array.
// Pigeonhole Sort
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void pigeonholeSort(int arrayOfNumbers[], int numberOfElements)
{
// Find the min and max values
int minimum = arrayOfNumbers[0];
int maximum = arrayOfNumbers[0];
for (int i = 1; i < numberOfElements; i++)
{
if (arrayOfNumbers[i] < minimum)
{
minimum = arrayOfNumbers[i];
}
if (arrayOfNumbers[i] > maximum)
{
maximum = arrayOfNumbers[i];
}
}
// Calculate the range
int range = maximum - minimum + 1;
// Create the pigeonholes
vector<int> holes[range];
// Put elements in their hole
for (int i = 0; i < numberOfElements; i++)
{
holes[arrayOfNumbers[i] - minimum].push_back(arrayOfNumbers[i]);
}
// Put the sorted elements back to the array
int index = 0;
for (int i = 0; i < range; i++)
{
vector<int>::iterator it;
for (it = holes[i].begin(); it != holes[i].end(); ++it)
{
arrayOfNumbers[index++] = *it;
}
}
}
void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; ++i)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}
int main(void)
{
int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
pigeonholeSort(arrayOfNumbers, numberOfElements);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
}
Comments