Python Program for Pigeonhole Sort

Pigeon-hole sorting is quite similar to Counting sorting. Pigeonhole sort moves the items to the bucket array before transferring them to the final destination.

In this tutorial, we are going to sort an array using the pigeonhole sorting method.

Pigeonhole Sort - Basic Introduction

The pigeonhole sorting method is typically selected to sort the list. If the number of elements in the list is equal to the potential key values in the list. It is a well-known sorting method for sorting lists where the number of elements in the list is about equal to the range of potential key values.

Let us now see the working of a pigeonhole sorting method:

1. We'll start by determining the array's maximum and lowest values. We can simply compute the range as (max-min + 1)
2. Now we'll make an empty array with the same dimensions as the range. Pigeonholes is the name given to this array because of its size.
3. We'll now iterate through the original array, placing each member in the appropriate slot. The index a[i]-mini is used to compute the pigeonhole of an element a[i].
4. Finally, we'll re-insert the filled gaps in the original array.
5. The array is now sorted.

Algorithm

As of now, we have a rough understanding of how pigeonhole sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Create a function pigeonhole_sort()
2. Find the minimum and maximum values among the elements present in the array.
3. Create a list of pigeonholes
4. Populate the pigeonholes.
5. Put the elements back into the array order.
6. The array is now sorted
7. Print the array.

Program for Pigeonhole Sort

As discussed above in the algorithm, let us now dive into the programming part of the pigeonhole sort operation influenced by the algorithm.

def pigeonhole_sort(a):
    minimum = min(a)
    maximum = max(a)
    s = maximum - minimum + 1
    h = [0] * s #holes
    for x in a:
        assert type(x) is int, "integers only please"
        h[x - minimum] += 1
    i = 0
    for c in range(s):
        while h[c] > 0:
            h[c] -= 1
            a[i] = c + minimum
            i += 1
 
# driver code
array = [9, 7, 2, 3, 4, 8, 6]
print("The original array is: ", array)
print("The Sorted order is : ", end = ' ')
pigeonhole_sort(array)      
for i in range(0, len(array)):
    print(array[i], end = ' ')

The original array is: [9, 7, 2, 3, 4, 8, 6]
The Sorted order is: 2 3 4 6 7 8 9

Conclusion

In this tutorial, we have performed a pigeonhole sort operation in python to sort an array. This program is a stable program and performs sorting operations in linear time. The time complexity of pigeonhole sort operation is O(n+K) and the space complexity of pigeonhole sort operation is O(n+K). The pigeonhole method will be a good choice if the number of items and their range is comparable.