Radix Sort is a non-comparative sorting algorithm that sorts data with integer keys by grouping the keys by individual digits which share the same significant position and value. Radix Sort works by using the counting sort as a subroutine to sort the input array elements. It is a stable sort which means that the relative order of equal elements is preserved after sorting.
How Radix Sort Works
Radix sort works by first sorting the input elements according to their least significant digit (LSD), then according to their second least significant digit, and so on until the most significant digit (MSD) is sorted. The sorting operation at each significant digit is performed using a stable sort algorithm such as counting sort.
For example, consider the following array of integers:
[170, 45, 75, 90, 802, 24, 2, 66]
The first step of the radix sort algorithm would sort the array according to the least significant digit (LSD) which is the rightmost digit in this case. The sorted array would look like:
[802, 2, 24, 45, 66, 170, 75, 90]
The second step would sort the array according to the second least significant digit which is the tens place in this case. The sorted array would look like:
[2, 24, 45, 66, 75, 90, 170, 802]
The final step would sort the array according to the most significant digit which is the hundreds place in this case. Since all the elements have been sorted in the previous steps, the final sorted array would be:
[2, 24, 45, 66, 75, 90, 170, 802]
Algorithm Implementation
The implementation of radix sort involves two main functions: counting sort and radix sort. The counting sort function is used as a subroutine by the radix sort function. The counting sort function sorts the input array elements based on a specified digit, while the radix sort function uses the counting sort function to sort the elements based on all significant digits.
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# Count occurrences of digits
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
# Cumulative count
for i in range(1, 10):
count[i] += count[i - 1]
# Build output array
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# Copy output array to input array
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
The counting sort function takes two arguments: the input array and the digit to sort by. The radix sort function takes only the input array as an argument.
The counting sort function sorts the input array elements based on a specified digit. It uses the digit to calculate the index of the corresponding count array element, and then increments the count at that index for each occurrence of that digit in the array. The cumulative count is then calculated by adding each count to the previous count. Finally, the output array is built by iterating over the input array from right to left, using the digit to calculate the index of the corresponding output array element, and then decrementing the count at that index. The output array is then copied back to the input array.
The radix sort function first determines the maximum element in the input array to determine the number of significant digits to sort by. It then iterates over each significant digit, calling the counting sort function to sort the input array based on that digit. The digit to sort by is determined by dividing the element by the current exponent (10 to the power of the current significant digit) and taking the remainder when divided by 10. After each iteration, the exponent is multiplied by 10 to move on to the next significant digit.
Time and Space Complexity
The time complexity of radix sort is O(d * (n + k)), where d is the number of significant digits, n is the number of elements in the input array, and k is the range of values for each digit. Since the range of values for each digit is constant (0 to 9), the time complexity can be simplified to O(d * n). Radix sort has a linear time complexity, which makes it faster than many other sorting algorithms for large input sizes.
The space complexity of radix sort is O(n + k), where n is the number of elements in the input array, and k is the range of values for each digit. The space complexity of radix sort is dependent on the space used by the counting sort subroutine. In the worst case, where all the elements have the same value, the space complexity is O(n).
Implementation Example
Let’s implement and run the radix sort algorithm on a sample array of integers.
arr = [170, 45, 75, 90, 802, 24, 2, 66] radix_sort(arr) print(arr)
The output of the above code should be:
[2, 24, 45, 66, 75, 90, 170, 802]
In the above example, we initialize an array of integers and pass it as an argument to the radix_sort function. The function sorts the elements of the array in ascending order based on their significant digits. Finally, we print the sorted array to the console.
