radix_sort.py

defcountingSortForRadix(inputArray, placeValue):
# We can assume that the number of digits used to represent
# all numbers on the placeValue position is not grater than 10
countArray= [0] *10
inputSize=len(inputArray)

# placeElement is the value of the current place value
# of the current element, e.g. if the current element is
# 123, and the place value is 10, the placeElement is
# equal to 2
foriinrange(inputSize): 
placeElement= (inputArray[i] //placeValue) %10
countArray[placeElement] +=1

foriinrange(1, 10):
countArray[i] +=countArray[i-1]

# Reconstructing the output array
outputArray= [0] *inputSize
i=inputSize-1
whilei>=0:
currentEl=inputArray[i]
placeElement= (inputArray[i] //placeValue) %10
countArray[placeElement] -=1
newPosition=countArray[placeElement]
outputArray[newPosition] =currentEl
i-=1

returnoutputArray

defradixSort(inputArray):
# Step 1 -> Find the maximum element in the input array
maxEl=max(inputArray)

# Step 2 -> Find the number of digits in the `max` element
D=1
whilemaxEl>0:
maxEl/=10
D+=1

# Step 3 -> Initialize the place value to the least significant place
placeVal=1

# Step 4
outputArray=inputArray
whileD>0:
outputArray=countingSortForRadix(outputArray, placeVal)
placeVal*=10
D-=1

returnoutputArray

input= [2,20,61,997,1,619]
print(input)
sorted=radixSort(input)
print(sorted)