Θ(n) where n is the total digit count
from random import choices
def countingSort(source:[], digits:[], scope:int) -> []:
counter = [0]*scope
amount = len(source)
for x in digits:
counter[x] += 1
for i in range(1, scope):
counter[i] += counter[i-1]
destination = [0]*amount
for i in reversed(range(amount)):
quantity = digits[i]
# index = count-1
destination[counter[quantity]-1] = source[i]
counter[quantity] -= 1
return destination
def radixSort(source:[], numOfDigits:int, scope:int)->[]:
amount = len(source)
dst = source
for i in range(numOfDigits):
digits = []
for x in dst:
temp = x // (scope ** i)
digit = temp % scope
digits.append(digit)
dst = countingSort(dst, digits, scope)
return dst
def digitCountOfFigure(figure:int)->int:
if figure == 0:
return 1
count = 0
while figure != 0:
count += 1
figure //= 10
return count
def variableDigitCountSort()->[]:
scope = 10
amount = 1000
digits = 3
src = choices(range(amount), k=amount)
groups = [[] for _ in range(digits)]
for x in src:
groups[digitCountOfFigure(x) - 1].append(x)
dst = []
for i in range(digits):
dst += radixSort(groups[i], i+1, scope)
return dst
