Program for Pigeonhole Sort using Python

by | Jun 23, 2021 | Python Programs

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

Program for Pigeonhole Sort using Python

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.

Author

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

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