Table of Contents
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 = [0] * 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.
0 Comments