TheAlgorithms-Python

1
"""
2
This is a pure Python implementation of the radix sort algorithm
3

4
Source: https://en.wikipedia.org/wiki/Radix_sort
5
"""
6

7
from __future__ import annotations
8

9
RADIX = 10
10

11

12
def radix_sort(list_of_ints: list[int]) -> list[int]:
13
    """
14
    Examples:
15
    >>> radix_sort([0, 5, 3, 2, 2])
16
    [0, 2, 2, 3, 5]
17

18
    >>> radix_sort(list(range(15))) == sorted(range(15))
19
    True
20
    >>> radix_sort(list(range(14,-1,-1))) == sorted(range(15))
21
    True
22
    >>> radix_sort([1,100,10,1000]) == sorted([1,100,10,1000])
23
    True
24
    """
25
    placement = 1
26
    max_digit = max(list_of_ints)
27
    while placement <= max_digit:
28
        # declare and initialize empty buckets
29
        buckets: list[list] = [[] for _ in range(RADIX)]
30
        # split list_of_ints between the buckets
31
        for i in list_of_ints:
32
            tmp = int((i / placement) % RADIX)
33
            buckets[tmp].append(i)
34
        # put each buckets' contents into list_of_ints
35
        a = 0
36
        for b in range(RADIX):
37
            for i in buckets[b]:
38
                list_of_ints[a] = i
39
                a += 1
40
        # move to next
41
        placement *= RADIX
42
    return list_of_ints
43

44

45
if __name__ == "__main__":
46
    import doctest
47

48
    doctest.testmod()
49