What is Pigeonhole Sort
Pigeonhole sort is a sorting algorithm that works by distributing elements of an unsorted list into a set of "pigeonholes" or buckets based on their values. For example, if you have a list of numbers from 1 to 10, you would create 10 pigeonholes, one for each number.
Then you would iterate through the unsorted list of numbers and place each number into its corresponding pigeonhole based on its value. So, if the number is 5, you would place it in the fifth pigeonhole.
Once all the numbers have been placed into their respective pigeonholes, you would then iterate through the pigeonholes in order and concatenate the elements back into a sorted list.
One important thing to note is that Pigeonhole sort works best when the range of values in the list is small compared to the number of elements in the list. If the range of values is too large, it can become inefficient.
Who invented it?
The exact origins of Pigeonhole sort are unclear, as it is a very old algorithm that has been known for centuries. However, it was formally described and analyzed in computer science literature by A. J. Lotka in 1926, and later independently rediscovered by John Knuth in the 1960s.
The algorithm gets its name from the concept of "pigeonholes", which refers to the idea that if you have more pigeons than pigeonholes, at least one of the pigeonholes must contain more than one pigeon. This idea is similar to how the algorithm works, as it distributes elements into pigeonholes based on their values and relies on the fact that if there are more elements than pigeonholes, at least one pigeonhole must contain more than one element.
Pseudocode
Pigeonhole_Sort(a[])
Find the minimum and maximum values in the array a[]
Let range = max - min + 1
Create an array of empty "pigeonholes" with size = range
Loop through the array a[] and place each element in the corresponding pigeonhole
for i = 0 to length(a) - 1
hole = a[i] - min
increment pigeonhole[hole]
Loop through the pigeonholes and concatenate the elements back into a sorted list
for i = 0 to range - 1
while pigeonhole[i] > 0
add min + i to the sorted list
decrement pigeonhole[i]
return sorted list
In this pseudocode, a[] represents the input array to be sorted, min and max are the minimum and maximum values in the array, range is the size of the range of values in the array, and pigeonhole[] is an array of empty "pigeonholes" with size range. The algorithm works by iterating through the input array, placing each element into its corresponding pigeonhole based on its value, and then concatenating the elements back into a sorted list by iterating through the pigeonholes in order.
Sample Code
// C++ code snippet
vector PigeonholeSort(vector& arr) {
// Find the minimum and maximum values in the array
int min_val = arr[0], max_val = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] < min_val) {
min_val = arr[i];
}
if (arr[i] > max_val) {
max_val = arr[i];
}
}
// Let range = max - min + 1
int range = max_val - min_val + 1;
// Create an array of empty "pigeonholes" with size = range
vector pigeonholes(range, 0);
// Loop through the array and place each element in the corresponding pigeonhole
for (int i = 0; i < arr.size(); i++) {
int hole = arr[i] - min_val;
pigeonholes[hole]++;
}
// Loop through the pigeonholes and concatenate the elements back into a sorted list
vector sorted_arr(arr.size());
int index = 0;
for (int i = 0; i < range; i++) {
while (pigeonholes[i] > 0) {
sorted_arr[index] = i + min_val;
pigeonholes[i]--;
index++;
}
}
return sorted_arr;
}
int main() {
// Example usage
vector arr = {8, 3, 5, 2, 9, 1, 4, 6, 7};
vector sorted_arr = PigeonholeSort(arr);
// Print the sorted array
for (int i = 0; i < sorted_arr.size(); i++) {
cout << sorted_arr[i] << " ";
}
cout << endl;
return 0;
}
# Python code snippet
def pigeonhole_sort(arr):
# Find the minimum and maximum values in the array
min_val, max_val = min(arr), max(arr)
# Let range = max - min + 1
range_ = max_val - min_val + 1
# Create an array of empty "pigeonholes" with size = range
pigeonholes = [0] * range_
# Loop through the array and place each element in the corresponding pigeonhole
for i in arr:
hole = i - min_val
pigeonholes[hole] += 1
# Loop through the pigeonholes and concatenate the elements back into a sorted list
sorted_arr = []
for i in range(range_):
while pigeonholes[i] > 0:
sorted_arr.append(i + min_val)
pigeonholes[i] -= 1
return sorted_arr
# Example usage
arr = [8, 3, 5, 2, 9, 1, 4, 6, 7]
sorted_arr = pigeonhole_sort(arr)
print(sorted_arr)
import java.util.ArrayList;
import java.util.List;
public class PigeonholeSort {
public static List pigeonholeSort(List arr) {
// Find the minimum and maximum values in the array
int minVal = arr.get(0), maxVal = arr.get(0);
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i) < minVal) {
minVal = arr.get(i);
}
if (arr.get(i) > maxVal) {
maxVal = arr.get(i);
}
}
// Let range = max - min + 1
int range = maxVal - minVal + 1;
// Create an array of empty "pigeonholes" with size = range
int[] pigeonholes = new int[range];
// Loop through the array and place each element in the corresponding pigeonhole
for (int i = 0; i < arr.size(); i++) {
int hole = arr.get(i) - minVal;
pigeonholes[hole]++;
}
// Loop through the pigeonholes and concatenate the elements back into a sorted list
List sortedArr = new ArrayList(arr.size());
for (int i = 0; i < range; i++) {
while (pigeonholes[i] > 0) {
sortedArr.add(i + minVal);
pigeonholes[i]--;
}
}
return sortedArr;
}
public static void main(String[] args) {
// Example usage
List arr = List.of(8, 3, 5, 2, 9, 1, 4, 6, 7);
List sortedArr = pigeonholeSort(arr);
// Print the sorted array
System.out.println(sortedArr);
}
}