TheAlgorithms-Python

1
# Python program to implement Pigeonhole Sorting in python
2

3
# Algorithm for the pigeonhole sorting
4

5

6
def pigeonhole_sort(a):
7
    """
8
    >>> a = [8, 3, 2, 7, 4, 6, 8]
9
    >>> b = sorted(a)  # a nondestructive sort
10
    >>> pigeonhole_sort(a)  # a destructive sort
11
    >>> a == b
12
    True
13
    """
14
    # size of range of values in the list (ie, number of pigeonholes we need)
15

16
    min_val = min(a)  # min() finds the minimum value
17
    max_val = max(a)  # max() finds the maximum value
18

19
    size = max_val - min_val + 1  # size is difference of max and min values plus one
20

21
    # list of pigeonholes of size equal to the variable size
22
    holes = [0] * size
23

24
    # Populate the pigeonholes.
25
    for x in a:
26
        assert isinstance(x, int), "integers only please"
27
        holes[x - min_val] += 1
28

29
    # Putting the elements back into the array in an order.
30
    i = 0
31
    for count in range(size):
32
        while holes[count] > 0:
33
            holes[count] -= 1
34
            a[i] = count + min_val
35
            i += 1
36

37

38
def main():
39
    a = [8, 3, 2, 7, 4, 6, 8]
40
    pigeonhole_sort(a)
41
    print("Sorted order is:", " ".join(a))
42

43

44
if __name__ == "__main__":
45
    main()
46