Radix sort is a non-comparative sorting algorithm that sorts data with integer keys by grouping the keys by individual digits. The algorithm sorts the input array digit by digit, from the least significant digit (LSD) to the most significant digit (MSD). Radix sort can be applied to data that can be sorted lexicographically, such as integers, words, or floating-point numbers.
The main steps of the radix sort algorithm are as follows:
- Grouping: Group the elements of the array based on the value of individual digits, starting from the rightmost digit (LSD) to the leftmost digit (MSD).
- Sorting: Sort the elements within each digit grouping, maintaining the relative order of elements with the same digit value.
- Combine: Combine the sorted groupings to produce the final sorted array.
Algorithm
The Radix sort algorithm sorts data with integer keys by grouping the keys by individual digits. Here is the algorithm for Radix sort:
radixSort(arr)
Find the maximum number in the array to determine
the number of digits
for i in range(number of digits of the maximum number):
Initialize empty buckets for each digit (0 to 9)
for j in range(length of the array):
Extract the digit at the current significant place
Place the element in the corresponding bucket
based on the extracted digit
Update the array by concatenating the
elements from all buckets
Working of Radix sort Algorithm
Sure, let’s walk through the process of Radix sort step by step with an example and corresponding diagrams. Consider the following array of integers:
170,45,75,90,802,24,2,66
Iteration 1 (Sorting by Ones Place):
- Create buckets for each digit (0-9).
- Group the numbers based on their ones place.
- Reconstruct the array based on the grouping.
170,90,802,2,24,45,75,66
Iteration 2 (Sorting by Tens Place):
- Create buckets for each digit (0-9).
- Group the numbers based on their tens place.
- Reconstruct the array based on the grouping.
802,2,24,45,66,170,75,90
Iteration 3 (Sorting by Hundreds Place):
- Create buckets for each digit (0-9).
- Group the numbers based on their hundreds place.
- Reconstruct the array based on the grouping.
2,24,45,66,75,90,170,802
The following diagram illustrates the step-by-step process of the Radix sort algorithm:
Initial Array:
170, 45, 75, 90, 802, 24, 2, 66
Iteration 1 (Sorting by Ones Place):
170, 90, 802, 2, 24, 45, 75, 66
Iteration 2 (Sorting by Tens Place):
802, 2, 24, 45, 66, 170, 75, 90
Iteration 3 (Sorting by Hundreds Place):
2, 24, 45, 66, 75, 90, 170, 802
Final Sorted Array:
2, 24, 45, 66, 75, 90, 170, 802
Radix sort complexity
The time complexity of Radix sort depends on the number of digits in the largest number in the array and the number of elements in the array:
| Case | Time Complexity |
|---|---|
| Best Case | Ω(n+k) |
| Average Case | θ(nk) |
| Worst Case | O(nk) |
Best Case Time Complexity: O(nk)
- The best case occurs when all numbers have the same number of digits. In this scenario, each element needs to be iterated through once for each digit. Therefore, the time complexity becomes O(nk), where n is the number of elements in the array, and k is the number of digits.
Average Case Time Complexity: O(nk)
- On average, Radix sort also has a time complexity of O(nk) since it iterates through each element for each digit. The performance is relatively consistent, making it suitable for large datasets.
Worst Case Time Complexity: O(nk)
- The worst case occurs when all elements have varying numbers of digits, and the algorithm must iterate through each element for each digit. The time complexity remains O(nk), where n is the number of elements in the array, and k is the number of digits.
Implementation of Radix sort
Below is a simple implementation of the Radix Sort algorithm in Java:
import java.util.Arrays;
public class RadixSort {
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max()
.getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10)
{
countSort(arr, exp);
}
}
public static void countSort(int[] arr, int exp)
{
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
Arrays.fill(count, 0);
for (int j : arr) {
count[(j / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] =
arr[i];
count[(arr[i] / exp) % 10]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] arr =
{170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original array: "
+ Arrays.toString(arr));
radixSort(arr);
System.out.println("Sorted array: "
+ Arrays.toString(arr));
}
}
