python-data-structures-and-algorithms/Sorting/Radix Sort/RadixSort.py at main · CPWu/python-data-structures-and-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def radixSort(array):
    if len(array) == 0:
        return array

    # get max value in array
    maxNumber = max(array)

    digit = 0
    while maxNumber / 10 ** digit > 0:
        countingSort(array, digit)
        digit += 1

    return array

def countingSort(array, digit):
    sortedArray = [0] * len(array)
    countArray = [0] * 10

    digitColumn = 10 ** digit
    for num in array:
        countIndex = (num // digitColumn) % 10
        countArray[countIndex] += 1

    for index in range(1, 10):
        countArray[index] += countArray[index - 1]

    for index in range(len(array) -1, -1, -1):
        countIndex = (array[index] // digitColumn) % 10
        countArray[countIndex] -= 1
        sortedIndex = countArray[countIndex]
        sortedArray[sortedIndex] = array[index]

    for index in range(len(array)):
        array[index] = sortedArray[index]

array = [8762, 654, 3008, 345, 87, 65, 234, 12, 2]
print(radixSort(array))