Radix Sort
Problem
Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. It sorts numbers from the least significant digit to the most significant digit, using a stable sort for each digit position.
Examples:
Example 1:
Input: arr = [170, 45, 75, 90, 802, 24, 2, 66]
Output: [2, 24, 45, 66, 75, 90, 170, 802]
Explanation: The algorithm sorts the array by processing each digit position from right to left.
Example 2:
Input: arr = [121, 432, 564, 23, 1, 45, 788]
Output: [1, 23, 45, 121, 432, 564, 788]
Explanation: The algorithm efficiently sorts the array by considering each digit position separately.
Solution
Intuition
- Radix Sort works by sorting numbers digit by digit, from the least significant digit (rightmost) to the most significant digit (leftmost).
- It uses a stable sorting algorithm (usually Counting Sort) as a subroutine to sort the numbers according to each digit.
- The algorithm processes all digits of the largest number in the array.
- Since it sorts based on digits rather than comparing elements, Radix Sort can achieve linear time complexity for a fixed number of digits.
Approach
- Find the maximum number in the array to determine the number of digits.
- For each digit position (starting from the least significant digit):
- - Sort the array based on the current digit position using a stable sort (like Counting Sort).
- - Move to the next digit position.
- Repeat until all digit positions are processed.
Complexity Analysis
- Time Complexity: O(d * (n + k)) where d is the number of digits, n is the number of elements, and k is the range of each digit (usually 10 for decimal numbers).
- Space Complexity: O(n + k) for the temporary arrays used in the counting sort subroutine.
Implementation
CPP
Run your code to see output here