TheAlgorithms-Python

1
"""
2
This is an implementation of Pigeon Hole Sort.
3
For doctests run following command:
4

5
python3 -m doctest -v pigeon_sort.py
6
or
7
python -m doctest -v pigeon_sort.py
8

9
For manual testing run:
10
python pigeon_sort.py
11
"""
12

13
from __future__ import annotations
14

15

16
def pigeon_sort(array: list[int]) -> list[int]:
17
    """
18
    Implementation of pigeon hole sort algorithm
19
    :param array: Collection of comparable items
20
    :return: Collection sorted in ascending order
21
    >>> pigeon_sort([0, 5, 3, 2, 2])
22
    [0, 2, 2, 3, 5]
23
    >>> pigeon_sort([])
24
    []
25
    >>> pigeon_sort([-2, -5, -45])
26
    [-45, -5, -2]
27
    """
28
    if len(array) == 0:
29
        return array
30

31
    _min, _max = min(array), max(array)
32

33
    # Compute the variables
34
    holes_range = _max - _min + 1
35
    holes, holes_repeat = [0] * holes_range, [0] * holes_range
36

37
    # Make the sorting.
38
    for i in array:
39
        index = i - _min
40
        holes[index] = i
41
        holes_repeat[index] += 1
42

43
    # Makes the array back by replacing the numbers.
44
    index = 0
45
    for i in range(holes_range):
46
        while holes_repeat[i] > 0:
47
            array[index] = holes[i]
48
            index += 1
49
            holes_repeat[i] -= 1
50

51
    # Returns the sorted array.
52
    return array
53

54

55
if __name__ == "__main__":
56
    import doctest
57

58
    doctest.testmod()
59
    user_input = input("Enter numbers separated by comma:\n")
60
    unsorted = [int(x) for x in user_input.split(",")]
61
    print(pigeon_sort(unsorted))
62