Python Pool: Pigeonhole Sort in Python With Algorithm and Code Snippet

In this article, we will dig into a sorting algorithm known as the pigeonhole sort in Python. So, what exactly is a pigeonhole sort? It is a sorting algorithm famously used for sorting the lists in which the number of elements in the list is approximately equal to the range of possible key values. Let us now understand the pigeonhole sort in detail.

Algorithm for Pigeonhole Sort in Python:

1. At first, we will find the maximum as well as the minimum value in the array. Finding the max and the min value, we can easily calculate the range as (max-min +1)
2. Now, we will create an empty array having the same size as the range. The space of the array is why this array is known as pigeonholes.
3. Now, we will iterate through the original array and put each element in its respective pigeonhole. The pigeonhole of an element a[i] is calculated as the index a[i]-mini
4. Lastly, in the initial array, we will reinsert the filled holes

Illustration of the Algorithm:

Let us consider an array having elements as [12, 16, 19, 10, 9]

Maximum element = 19

Minimum element = 9

Thus, range = ( 19 – 9 )= 10

Now, we will create a pigeonhole array having index from 0-10

Now, that the pigeonhole array is created we will put each element from the original array into their respective pigeonhole

Pigeonhole Algorithm Illustration

Here, B is the pigeonhole array having index 0-10

In the respective pigeonholes, we will fill the elements from the original array

Lastly, in the initial array we will reinsert the filled holes, thus giving a sorted array.

Implementation of Pigeonhole Sort Algorithm in Python:

def pigeonhole_sort(a):
    minimum = min(a)
    maximum = max(a)
    size = maximum - minimum + 1
    pigeonholes = [0] * size
    for i in a:
        pigeonholes[i - minimum] += 1
    j = 0
    for count in range(size):
        while pigeonholes[count] > 0:
            pigeonholes[count] -= 1
            a[j] = count + minimum
            j += 1
             
 
a = [12, 16, 19, 10,  9]
print("The array is :")
print(a)
print("Sorted array is :")
pigeonhole_sort(a)
print(a)

Output:

Output for pigeonhole sort

explanation of the code:

• At first, we have found the maximum and minimum value, and from that, we have calculated the size of the pigeonhole array.
• After this, for the index corresponding to which the elements are present in the original array, we will insert the value 1 in the pigeonhole array.
• And finally, in the original array, we will reinsert the filled holes, thus giving a sorted array.

Analysis of the Pigeonhole Sort Algorithm in Python:

• Time complexity: O(n+K)
• Space complexity: O(n+K)

Note:

• n – Size of array
• K – Range of value

Advantages:

• Pigeonhole sort is a non-comparison based sort making it faster in application
• It is a stable sorting algorithm
• It performs sorting in linear time

Disadvantages:

• It isn’t easy to know the range of the numbers to sort
• This number might only work with zero and positive integers

Must Read

• Insertion Sort in Python [Program, Algorithm, Example]
• Understanding Python Bubble Sort with examples
• Shell Sort Algorithm and Program in Python
• Understanding Strand Sort in Python With Example

Conclusion:

In this article, we learned about the pigeonhole algorithm. Its implementation in python, its advantages as well as its disadvantages. All sorting algorithms come with their own pros and cons. If the number of items and its range is similar, the pigeonhole algorithm will be a wise choice.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

The post Pigeonhole Sort in Python With Algorithm and Code Snippet appeared first on Python Pool.

from Planet Python
via read more