# Program for Pigeonhole Sort using Python

## Introduction

The pigeonhole sorting algorithm is used where number of elements and number of key value will be approximately same.

## Program

```def sort(ip_arr):
arr_min = min(ip_arr)
arr_max = max(ip_arr)
arr_size = arr_max - arr_min + 1
holes =  * arr_size
for x in ip_arr:
assert type(x) is int, "integers only"
holes[x - arr_min] += 1
i = 0
for j in range(arr_size):
while holes[j] > 0:
holes[j] -= 1
ip_arr[i] = j + arr_min
i += 1

ip_arr = [54, 26, 81, 1]
sort(ip_arr)
print("The sorted array is :")
for i in range(len(ip_arr)):
print(ip_arr[i])```

## Output ## Explanation

The above code follows the following steps:

• We have maximum and minimum values in the array. From max and min values we will calculate the range max – (min + 1).
• Construct the array of size range that we have calculated.
• Traverse through the elements of array, and place it at index arr[i] – min.
• When all the elements are sorted in the new pigeonhole array, traverse through all the elements of pigeonhole array in order and place it back to the original array.
• Return the array with sorted elements.

This site uses Akismet to reduce spam. Learn how your comment data is processed.