def countingSort(arr, exp1): ''' This function sorts the array arr using counting sort.
Args: arr: The array to be sorted. exp1: The exponent of the current digit.
Returns: The sorted array. '''
# Get the length of the array. n = len(arr)
# Create an output array of the same size as the input array. output = [0] * (n)
# Create a count array to store the number of occurrences of each digit. count = [0] * (10)
# Iterate over the input array and increment the count array at the index of the current digit. for i in range(0, n): index = (arr[i] // exp1) count[int((index) % 10)] += 1
# Iterate over the count array and update it to store the cumulative sum of the counts. for i in range(1, 10): count[i] += count[i - 1]
# Iterate over the input array in reverse order and store the elements in the output array, # starting at the index of the current digit. i = n - 1 while i >= 0: index = (arr[i] // exp1) output[count[int((index) % 10)] - 1] = arr[i] count[int((index) % 10)] -= 1 i -= 1
# Copy the output array to the input array. for i in range(0, len(arr)): arr[i] = output[i]
def radixSort(arr): ''' This function sorts the array arr using radix sort.
Args: arr: The array to be sorted.
Returns: The sorted array. '''
# Get the maximum value in the array. max1 = max(arr)
# Start with the exponent 1 and iterate until the maximum value is not divisible by the exponent. exp = 1 while max1 // exp > 0: # Sort the array using counting sort for the current exponent. countingSort(arr, exp) # Increase the exponent by 1. exp *= 10
# Create an array of numbers. arr = [170, 45, 75, 90, 802, 24, 2, 66]
# Sort the array using radix sort. radixSort(arr)
# Print the sorted array. for i in range(len(arr)): print(arr[i], end=' ')
