Implementation of Pigeonhole Sort in Python

In this tutorial, we will learn about performing the Implementation of  Pigeonhole Sort in Python. We will have a look at the Pigeonhole logarithm, it’s working, and implementation in Python.

Pigeonhole sorting is used for sorting lists of elements where the total number of elements (n) and the length of possible key values (m) are approximately the same.

Time Complexity: O(n+m)

Let’s look at an example to understand the concept of Pigeonhole sort.

Assuming we are sorting the given key-value pairs by their first elements or keys.

  • (9, “Apple”)
  • (2, “Mango”)
  • (7, “Guava”)
  • (4, “Orange”)

Here, minimum key = 2 and maximum key = 9

For each value between 2 and 9 we initialize a pigeonhole and move each element to its pigeonhole:

  • 2: (2, “Mango”)
  • 3:
  • 4:(4, “Orange”)
  • 5:
  • 6:
  • 7: (7, “Guava”)
  • 8:
  • 9: (9, “Apple”)

Now iterate over Pigeonhole array in order and put elements back to the original list.

Algorithm :

  1. Iterate through the given list to find the least and greatest values in the array ‘a’.
  2. Let least element = ‘mn’ and greatest element b = ‘mx’.
  3. Let the range of possible values = ‘ mx+mn-1 ‘.
  4. Declare an array that is initialized with null pigeonholes the same size as of the range. Let array be named as ‘pihole’.
  5. Iterate through array again. Put each element in its Pigeonhole.
  6. An element at position a[i] in the array is put in the hole at index a[i] – mn.
  7. Now iterate over Pigeonhole array ie ‘pinhole’ array and put elements back into original array ‘a’.

NOTE : Ignore the empty holes in pihole array while executing step 7.

Python function for implementing Pigeonhole sorting:

def pigeonhole_sorting(b) -> None:
    mn = min(b)
    range = max(b) - mn + 1
    hole = [0] * size
    for z in b:
        holes[z - mn] += 1
    i = 0
    for count in range(size):
        while hole[count] > 0:
            hole[count] -= 1
            b[i] = count + mn
            i += 1

 

Also, read: Python code for sorting contents of a text file

Leave a Reply

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