As the name implies, this algorithm uses the Pigeonhole Principle to sort items. Although this algorithm is not practically preffered, it strongly demonstrates the wonders of maths.
The strange thing about Pigeonhole Sort is that its performace not only depends on the input size (normal for all other algorithms), but on the input range as well. This means that Pigeonhole Sort will face a hard time sorting data that is spread over a large range. The average performance with respect to time is
O(n + r), where
n is the input size and
r is the range of input i.e.,
max - min.
The algorithms starts with
r + 1 empty holes, and then continues to populate them. Holes are numbered such that the minimum value will be in hole
0 while the largest one will be placed in hole
r. Each hole is marked with the number of items it contains which shows how many times a specific value is repeated. The algorithm then contines by placing the values in correct order based on their hole number.
Consider a list:
[1, 6, 9, 5, 4, 6]
n = 6
9 - 1 = 8
Hence, we have 9 empty holes, or say holes =
[0, 0, 0, 0, 0, 0, 0, 0, 0]
The algorithm will now iterate over all the values and mark the index
x - min of the list
x is a value from list and
min is the smallest value.
[_, _, _, _, _, 2, _, _, _]. This means that we have 2 6’s in our list.
After iterating over all the items, we have:
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[1, 0, 0, 1, 1, 2, 0, 0, 1]
Now, Pigeonhole Sort will visit each hole, and copy the values there to another list. This list will now be sorted.
[1, 4, 5, 6, 6, 9]
As you can see a lot of holes are empty, this algorithm requires a lot of space even for a small but widely spread data.
See the animation to understand how it really works.
I have two methods for implementing Pigeonhole Sort in Python: one is a special case.
def pigeonsort(values): # size of range of values in the list (ie, number of pigeonholes we need) _min = min(values) _max = max(values) _range = _max - _min + 1 # pigeonholes '''holes = [0 for i in range(_range)]''' holes =  * _range # populate the holes for x in values: holes[x - _min] += 1 # new sorted list, putting elements back to save space i = 0 for count in range(_range): while holes[count] > 0: #copy all elements from each hole holes[count] -= 1 values[i] = count + _min i += 1 # either print values # or return values
This method works iff the list has continuous and not-repeating values.
def pigeonsort( values ): _min = min(values) _max = max(values) _range = _max - _min # holes = [0 for i in range(_range + 1)] holes =  * _range # filling holes for value in values: holes[ value - _min ] = value #moving back to original; in order values = [value for value in holes] return values