Python Program for Pigeonhole Sort

Last Updated : 12 Sep, 2023

Pigeonhole Sort is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same. It requires O(n + Range) time where n is number of elements in input array and ‘Range’ is number of possible values in array.

Python Program for Pigeonhole Sort

Working of Algorithm :

Find minimum and maximum values in array. Let the minimum and maximum values be ‘min’ and ‘max’ respectively. Also find range as ‘max-min-1’.
Set up an array of initially empty “pigeonholes” the same size as of the range.
Visit each element of the array and then put each element in its pigeonhole. An element arr[i] is put in hole at index arr[i] – min.
Start the loop all over the pigeonhole array in order and put the elements from non- empty holes back into the original array.

Python3

# Python program to implement Pigeonhole Sort  
  
# source code : "https://en.wikibooks.org/wiki/ 
# Algorithm_Implementation/Sorting/Pigeonhole_sort" 
def pigeonhole_sort(a): 
    # size of range of values in the list 
    # (ie, number of pigeonholes we need) 
    my_min = min(a) 
    my_max = max(a) 
    size = my_max - my_min + 1
  
    # our list of pigeonholes 
    holes = [0] * size 
  
    # Populate the pigeonholes. 
    for x in a: 
        assert type(x) is int, "integers only please"
        holes[x - my_min] += 1
  
    # Put the elements back into the array in order. 
    i = 0
    for count in range(size): 
        while holes[count] > 0: 
            holes[count] -= 1
            a[i] = count + my_min 
            i += 1
              
  
a = [8, 3, 2, 7, 4, 6, 8] 
print("Sorted order is : ", end =" ") 
  
pigeonhole_sort(a) 
          
for i in range(0, len(a)): 
    print(a[i], end =" ")

Output

Sorted order is : 2 3 4 6 7 8 8

Please refer complete article on Pigeonhole Sort for more details

GeeksforGeeks

Improve

Previous Article

Python Program for Bitonic Sort

Python Program for Comb Sort

Similar Reads

Python Program for Odd-Even Sort / Brick Sort

This is basically a variation of bubble-sort. This algorithm is divided into two phases- Odd and Even Phase. The algorithm runs until the array elements are sorted and in each iteration two phases occurs- Odd and Even Phases. In the odd phase, we perform a bubble sort on odd indexed elements and in the even phase, we perform a bubble sort on even i

Sort a Dictionary Without Using Sort Function in Python

As we all know Dictionaries in Python are unordered by default, which means they can’t be sorted directly. However, we can sort the keys or values of a dictionary and create a new sorted dictionary from the sorted keys or values. We can sort a list in a Dictionary using the inbuilt dictionary sort() function. But in this article, we will learn how

Python program to Sort a List of Tuples in Increasing Order by the Last Element in Each Tuple

The task is to write a Python Program to sort a list of tuples in increasing order by the last element in each tuple. Input: [(1, 3), (3, 2), (2, 1)] Output: [(2, 1), (3, 2), (1, 3)] Explanation: sort tuple based on the last digit of each tuple. Methods #1: Using sorted(). Sorted() method sorts a list and always returns a list with the elements in

Python Program for Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array. Python Program for Selection SortThe provided Python code demonstrates the Selection Sort algorithm. Selection Sort has a time

Python Program for Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. Python Program for Insertion SortThe insertionSort function takes an array arr as input. It first calculates the length of the array (n). If the length is 0 or 1, the function returns immediately as an array with 0 or 1 element is considered already

Python Program for Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then do some arithmetic to calculate the position of each object in the output sequence. Python Program for Counting SortThe provided Python code demonstrates Counting Sort, a non-comp

Python Program for Radix Sort

In this article we are going to see Radix Sort with Python Radix Sort Algorithm PythonThe provided Python code implements Radix Sort, a non-comparative sorting algorithm that works by distributing elements into buckets based on their individual digits. The code defines a countingSort function, which performs counting sort based on the digit represe

Python Program for Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. C/C++ Code # Python program for counting sort # The main function that sort the given string

Python Program for Bitonic Sort

Bitonic Sequence: A sequence is called Bitonic if it is first increasing, then decreasing. In other words, an array arr[0..n-i] is Bitonic if there exists an index i where 0<=i<=n-1 such that x0 <= x1 …..<= xi and xi >= xi+1….. >= xn-1 A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty.

Python Program for Bitonic Sort

Bitonic Sequence: A sequence is called Bitonic if it is first increasing, then decreasing. In other words, an array arr[0..n-i] is Bitonic if there exists an index i where 0<=i<=n-1 such that x0 <= x1 …..<= xi and xi >= xi+1….. >= xn-1 A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty.

Article Tags :