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.
Brief description of working:
We create a separate array called as “pigeonholes” with a “range” size.
The “range” size that is taken by subtracting Maximum value of the array with the minimum value.
By doing so, 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.
Detailed explanation of Working:
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 “pigeonholeArray” 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]
Solution 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 elelments 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; }
Output:
Output 1: 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
Running time at worst case for Pigeon Hole sort
O(n+2^k)
Further Reading: