Python Program for Pigeonhole Sort
Pigeonhole sorting 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.
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.
# 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