Sorting means arranging things in order like putting your books by height or your clothes by color. In computer science sorting helps organize data to make it easier and faster to use. You may have heard of Bubble Sort, Quick Sort or Merge Sort. But have you ever heard of something called Pigeonhole Sort. It sounds funny but it is actually a real and clever way of sorting numbers.
This blog will explain what Pigeonhole Sort is how it works and when to use it. Don’t worry we will keep it super simple We will also show you how fast or slow it is write a small Python program for it and share when it is a good choice or a bad one. If you are a student or someone just curious about sorting stuff using code this blog is for you. Let us jump into the world of Pigeonhole Sort.
What is Pigeonhole Sort Algorithm?
Pigeonhole Sort is a simple sorting technique that works best when the number of elements you want to sort is close to the number of possible values they can take. For example, if you are sorting the ages of students in a class and all ages are between 10 and 15, then Pigeonhole Sort can be super fast and efficient.
It is based on a basic idea called the Pigeonhole Principle which says that if you have more pigeons than pigeonholes, at least one pigeonhole will have more than one pigeon. In sorting, this means putting each number into its right position or bucket based on its value just like how each pigeon goes into its own pigeonhole.
The algorithm creates a list of empty buckets then puts each number into the correct bucket. After that it puts all the numbers back together in order.
How Pigeonhole Sort Works?
Pigeonhole Sort works in a few simple steps. It is all about placing elements into holes or buckets and then collecting them back in order. Here’s how it works step by step:
Step-by-Step Process
- Find the minimum and maximum values in the array.
- Calculate the range by subtracting the minimum from the maximum and adding 1.
- Create empty buckets (also called pigeonholes) for each value in the range.
- Place each element in its appropriate bucket using its value.
- Go through the buckets one by one and collect the elements back in order.
Let’s understand this with a simple example.
arr = [8, 3, 2, 7, 4, 6, 8]
Bucket[0] → [2] (2 – 2 = 0)
Bucket[1] → [3] (3 – 2 = 1)
Bucket[2] → [4] (4 – 2 = 2)
Bucket[3] → []
Bucket[4] → [6] (6 – 2 = 4)
Bucket[5] → [7] (7 – 2 = 5)
Bucket[6] → [8, 8] (8 – 2 = 6)
Time and Space Complexity of Pigeonhole Sort
| Case | Time Complexity | Explanation |
| Best Case | O(n + Range) | When the range of elements is small and elements are evenly distributed. |
| Average Case | O(n + Range) | On average it still depends on both input size and value range. |
| Worst Case | O(n + Range) | If the range is large then extra space and time is used for empty buckets. |
| Space Complexity | O(n + Range) | Extra space is required to create buckets (pigeonholes). |
Python Code for Pigeonhole Sort
Let’s say you have a bunch of numbers and you want to sort them in order. Instead of comparing each number again and again like Bubble Sort, Pigeonhole Sort finds the smallest and biggest number first.
Then it makes empty boxes (buckets) for all the numbers in between. Each number is placed in its matching box. Finally, it collects all the numbers from the boxes in order and gives you the sorted list. It’s like sorting socks into drawers labeled with sizes and then pulling them out one by one in order.
def pigeonhole_sort(arr):
if not arr:
return arr
min_val = min(arr)
max_val = max(arr)
size = max_val - min_val + 1
holes = [[] for _ in range(size)]
for number in arr:
holes[number - min_val].append(number)
i = 0
for hole in holes:
for number in hole:
arr[i] = number
i += 1
return arr
arr = [8, 3, 2, 7, 4, 6, 8]
sorted_arr = pigeonhole_sort(arr)
print("Sorted array:", sorted_arr)
Advantages of Pigeonhole Sort Algorithm
- Pigeonhole Sort is very fast when the numbers you want to sort are close to each other.
- The idea is easy to understand because you just put numbers into buckets and then take them out in order.
- It does not need to compare numbers one by one like other sorting methods do.
- It keeps the original order of numbers that are the same, which is helpful sometimes.
- This method works best when you have a small range of numbers to sort.
Disadvantages of Pigeonhole Sort Algorithm
- Pigeonhole Sort uses a lot of extra space because it needs buckets for every number in the range.
- If the range of numbers is very large, it becomes slow and wastes memory.
- It is not good for sorting numbers that are spread out or very different from each other.
- The algorithm is not suitable for sorting things like strings or complex data easily.
- It can be less efficient than other sorting methods when the range of input values is much bigger than the number of items.
Frequently Asked Questions
Is Pigeonhole Sort a comparison-based sorting algorithm?
No, Pigeonhole Sort is not comparison-based. It sorts by placing elements into buckets based on their values.
When should I use Pigeonhole Sort?
Use it when you have numbers that are close together and the range of values is small.
Can Pigeonhole Sort handle negative numbers?
Yes, it can handle negative numbers by adjusting the buckets based on the minimum value.
Is Pigeonhole Sort stable?
Yes, it is stable if you insert elements in order into the buckets and collect them back properly.
How is Pigeonhole Sort different from Counting Sort?
Both use buckets, but Counting Sort counts frequencies, while Pigeonhole Sort places elements directly into buckets.
Conclusion
Pigeonhole Sort is a cool and simple sorting method that works best when your numbers are close together and the range is small. It sorts by putting each number into its own bucket and then collecting them in order. While it is fast and easy to understand, it can use a lot of extra space if the range of numbers is big. So, it’s not always the best choice for every sorting job. But if your data fits well, Pigeonhole Sort can save you time and effort. Now you know how it works, its pros and cons, and even how to code it in Python. Try it out and see for yourself.