TheAlgorithms-Python

1
"""
2
This is pure Python implementation of counting sort algorithm
3
For doctests run following command:
4
python -m doctest -v counting_sort.py
5
or
6
python3 -m doctest -v counting_sort.py
7
For manual testing run:
8
python counting_sort.py
9
"""
10

11

12
def counting_sort(collection):
13
    """Pure implementation of counting sort algorithm in Python
14
    :param collection: some mutable ordered collection with heterogeneous
15
    comparable items inside
16
    :return: the same collection ordered by ascending
17
    Examples:
18
    >>> counting_sort([0, 5, 3, 2, 2])
19
    [0, 2, 2, 3, 5]
20
    >>> counting_sort([])
21
    []
22
    >>> counting_sort([-2, -5, -45])
23
    [-45, -5, -2]
24
    """
25
    # if the collection is empty, returns empty
26
    if collection == []:
27
        return []
28

29
    # get some information about the collection
30
    coll_len = len(collection)
31
    coll_max = max(collection)
32
    coll_min = min(collection)
33

34
    # create the counting array
35
    counting_arr_length = coll_max + 1 - coll_min
36
    counting_arr = [0] * counting_arr_length
37

38
    # count how much a number appears in the collection
39
    for number in collection:
40
        counting_arr[number - coll_min] += 1
41

42
    # sum each position with it's predecessors. now, counting_arr[i] tells
43
    # us how many elements <= i has in the collection
44
    for i in range(1, counting_arr_length):
45
        counting_arr[i] = counting_arr[i] + counting_arr[i - 1]
46

47
    # create the output collection
48
    ordered = [0] * coll_len
49

50
    # place the elements in the output, respecting the original order (stable
51
    # sort) from end to begin, updating counting_arr
52
    for i in reversed(range(coll_len)):
53
        ordered[counting_arr[collection[i] - coll_min] - 1] = collection[i]
54
        counting_arr[collection[i] - coll_min] -= 1
55

56
    return ordered
57

58

59
def counting_sort_string(string):
60
    """
61
    >>> counting_sort_string("thisisthestring")
62
    'eghhiiinrsssttt'
63
    """
64
    return "".join([chr(i) for i in counting_sort([ord(c) for c in string])])
65

66

67
if __name__ == "__main__":
68
    # Test string sort
69
    assert counting_sort_string("thisisthestring") == "eghhiiinrsssttt"
70

71
    user_input = input("Enter numbers separated by a comma:\n").strip()
72
    unsorted = [int(item) for item in user_input.split(",")]
73
    print(counting_sort(unsorted))
74