In this chapter we shall learn about below topics:
6.1 Definition
6.2 Steps for performing Pigeonhole Sort
6.3 Understanding Pigeonhole Sort with an example
6.4 Implementation of Pigeonhole Sort in C
6.5 Output of the program
6.6 Time complexity analysis of Pigeonhole Sort
6.1 Definition
Pigeonhole sort is an interesting algorithm that works on integer numbers not floating value.
It works best when all the keys [elements in array] are unique.
6.2 Steps for performing Pigeonhole Sort
We create a separate array or “pigeonholes” of “range” size that is taken by subtracting Maximum value of the array with the minimum value.
Hence we shall be sure that other elements inside the array fall under Max and Min value.
Then we shall place the elements from the original array, into the pigeonhole array at the index by using the result from “original_array[i] – Min_element”.
At the end we shall copy the elements from the pigeonhole array to original array.
6.3 Understanding Pigeonhole Sort with an example
We take below variables:
Original_array: Has original unsorted array
Min_value: Has the minimum element of the array.
Max_value: Has the maximum element of the array.
Range = [Max_value – Min_value ] + 1
PigeonHole_array: PigeonHole array having “range” of spaces.
Steps:
Suppose we have the array [8, 5, 4, 3, 2, 1]
Hence:
Max = 8
Min = 1
Range = [ 8 - 1] + 1 = 8 Holes.
pigeonholeArray [0, 0, 0, 0, 0, 0, 0, 0]Pass 1:
i = 0
index = a[0] - Min_value + 1
= 8 - 1 + 1
=8
Hence place the element of a[0] in pigeonholeArray index 8
pigeonholeArray [0, 0, 0, 0, 0, 0, 0, 8]Pass 2:
i = 1
index = a[1] - Min_value + 1
= 5 - 1 + 1
=5
Hence place the element of a[1] in pigeonholeArray index 5
pigeonholeArray [0, 0, 0, 0, 5, 0, 0, 8]Pass 3:
i = 2
pigeonholeArray [0, 0, 0, 4, 5, 0, 0, 8]Pass 4:
i = 3
pigeonholeArray [0, 0, 3, 4, 5, 0, 0, 8]Pass 5:
i = 4
pigeonholeArray [0, 2, 3, 4, 5, 0, 0, 8]Pass 6:
i = 5
pigeonholeArray [1, 2, 3, 4, 5, 0, 0, 8]at the end copy the elements from the “pigeonhole Array” to original array, whose value is greater than 0. Final resulting array will be a sorted one.
Final array[1, 2, 3, 4, 5, 8]6.4 Implementation of Pigeonhole Sort in C
#include<stdio.h>
#define MAX_ELEMENTS 100
void pigeonHoleSort (int arr[], int length)
{
int pigeonHoleArray[ MAX_ELEMENTS ] = {0};
int *temp_array = arr;
int max_element = 0;
int min_element = 0;
int itr;
int range = 0;
// Get the min_element and max_element from the given array
for (itr = 0; itr < length; itr ++)
{
if (arr[itr] < min_element)
min_element = arr[itr];
if (arr[itr] > max_element)
max_element = arr[itr];
}
// Get the range
range = ( max_element - min_element ) + 1;
// Initialize the pigeonHoleArray with zero
for ( itr = 0; itr < range; itr++)
{
pigeonHoleArray [itr] = 0;
}
// place the elements in pigeonHoleArray
for ( itr = 0; itr < length; itr++, temp_array++)
{
pigeonHoleArray [ *temp_array - min_element ] += 1;
}
// copy from pigeonHoleArray to original array
for (itr = 0, temp_array = &arr[0]; itr < range; itr++)
{
while (pigeonHoleArray[itr] > 0)
{
pigeonHoleArray[itr]--;
*temp_array++ = itr + min_element;
}
}
}
void printArray(int arr[] , int length)
{
int itr = 0;
printf("The sorted array is \n");
for (itr = 0; itr < length; itr++)
{
printf("%d", arr[itr] );
}
printf("\n");
}
int main(int argc, char const *argv[])
{
int arr [ MAX_ELEMENTS ] = {0};
int length = 0;
int itr = 0;
printf("Enter number of elements of the array \n");
scanf ("%d", &length);
printf("Enter the elements\n");
for (itr = 0; itr < length; itr++)
{
scanf("%d", &arr[itr] );
}
pigeonHoleSort(arr, length);
printArray(arr, length);
return 0;
}
6.5 Output of the program
Enter number of elements of the array
4
Enter the elements
4
3
2
1
The sorted array is
1234
Output 2:
Enter number of elements of the array
7
Enter the elements
8
6
5
4
3
2
1
The sorted array is
1234568
6.6 Time complexity analysis of Pigeonhole Sort
In the worst case, the time taken will be n+2^k.