A visualisation of Radix sort algorithm from Determining the difficulty of accelerating problems on a GPU¶
See also the Geeks for Geeks page of Radix Sort
Radix sort is a sorting algorithm that sorts number digits by digits starting from the least import digit (rightest) to the most import digit (leftest). It does the sort without comparing the number among each other but just by associating each number to the corresponding group (0-9) for the current digit.
def radixSort(arr):
def countingSort(arr, digit_value):
output = [0] * (len(arr)) # output array will have sorted arr
count = [0] * (10) # initialize count array as 0 (for each digit its count among number)
# Store count of occurrences of each digit 0, 1, 2, ...., 9
for i in range(len(arr)):
index = arr[i] // digit_value
count[index % 10] += 1
# Change count[i] so that count[i] now contains actual position of this digit in output array (cumsum)
for i in range(1, 10):
count[i] += count[i - 1]
# Build the output array
i = len(arr) - 1 # start with last current element (last value given the less important digits)
while i >= 0:
index = arr[i] // digit_value
output[count[index % 10] - 1] = arr[i] # store to its new position
count[index % 10] -= 1 # decrease position for digit index % 10 by 1
i -= 1
# Copying the output array to arr[], so that arr now contains sorted numbers
i = 0
for i in range(0, len(arr)):
arr[i] = output[i]
# Find the maximum number to know number of digits
max_value = max(arr)
# Do counting sort for every digit. Note that instead of passing digit number, current digit value is passed
digit_value = 1
while max_value / digit_value >= 1:
countingSort(arr, digit_value)
digit_value *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr)
print(arr)
[2, 24, 45, 66, 75, 90, 170, 802]