Pigeonhole Sort Implementation in Python

Pigeonhole sort is a sorting algorithm that works by distributing elements of an array into a set of pigeonholes. The number of pigeonholes used is determined by the range of the elements in the array. Each pigeonhole is then sorted individually and the elements are gathered back into the original array in order. This algorithm has a time complexity of O(n + Range) where n is the number of elements in the array and Range is the difference between the largest and smallest elements in the array.

How Pigeonhole Sort Works

The algorithm works by following these steps:

1. Determine the range of the input array.
2. Create an array of empty “pigeonholes” equal in size to the range determined in step 1.
3. Iterate over the input array and place each element in the corresponding pigeonhole based on its value.
4. Iterate over the pigeonholes in order and place the elements back into the original array in order.

Pigeonhole Sort Implementation

Here’s the implementation of Pigeonhole Sort in Python:

def pigeonhole_sort(arr):
    # Step 1 - Determine the range of the input array
    min_val = min(arr)
    max_val = max(arr)
    range_val = max_val - min_val + 1
    
    # Step 2 - Create an array of empty pigeonholes
    holes = [0] * range_val
    
    # Step 3 - Iterate over the input array and place each element in the corresponding pigeonhole
    for num in arr:
        holes[num - min_val] += 1
    
    # Step 4 - Iterate over the pigeonholes in order and place the elements back into the original array
    i = 0
    for j in range(range_val):
        while holes[j] > 0:
            arr[i] = j + min_val
            holes[j] -= 1
            i += 1
    return arr

Let’s break down the implementation and understand each step:

Step 1 – Determine the range of the input array

In this step, we determine the range of the input array by finding the minimum and maximum values in the array and calculating the difference between them.

min_val = min(arr)
max_val = max(arr)
range_val = max_val - min_val + 1

Step 2 – Create an array of empty pigeonholes

In this step, we create an array of empty pigeonholes equal in size to the range of the input array.

holes = [0] * range_val

Step 3 – Iterate over the input array and place each element in the corresponding pigeonhole

In this step, we iterate over the input array and place each element in the corresponding pigeonhole based on its value.

for num in arr:
    holes[num - min_val] += 1

Step 4 – Iterate over the pigeonholes in order and place the elements back into the original array

In this step, we iterate over the pigeonholes in order and place the elements back into the original array in order.

i = 0
for j in range(range_val):
    while holes[j] > 0:
        arr[i] = j + min_val
        holes[j] -= 1
        i += 1

Here, we use two variables i and j. i is used to keep track of the current position in the original array, and j is used to iterate over the pigeonholes. We use a while loop to iterate over each pigeonhole until it is empty. For each non-empty pigeonhole, we place its corresponding element back into the original array and decrement the count of that pigeonhole. We continue this process until all pigeonholes are empty and all elements have been placed back into the original array.

Time and Space Complexity

Pigeonhole sort has a time complexity of O(n + Range) where n is the number of elements in the array and Range is the difference between the largest and smallest elements in the array. The space complexity is also O(n + Range) because we use an additional array of size Range to store the pigeonholes.

Example Run

Let’s see an example run of the algorithm to understand how it works:

arr = [8, 3, 2, 7, 4, 6, 8]

# Step 1 - Determine the range of the input array
min_val = 2
max_val = 8
range_val = 7

# Step 2 - Create an array of empty pigeonholes
holes = [0] * 7

# Step 3 - Iterate over the input array and place each element in the corresponding pigeonhole
for num in arr:
    holes[num - 2] += 1

# Step 4 - Iterate over the pigeonholes in order and place the elements back into the original array
i = 0
for j in range(7):
    while holes[j] > 0:
        arr[i] = j + 2
        holes[j] -= 1
        i += 1

print(arr)

The output of the above code will be:

[2, 3, 4, 6, 7, 8, 8]

As we can see, the input array has been sorted in ascending order using the Pigeonhole Sort algorithm.

Conclusion

Pigeonhole sort is a simple but efficient algorithm for sorting arrays with a small range of values. It has a time complexity of O(n + Range) which makes it efficient for small input sizes. Its space complexity is also O(n + Range) which is reasonable for most practical applications. It’s important to note that the algorithm assumes that the range of the input array is small, otherwise it can become inefficient.