Radix Sort
A non-comparative sorting algorithm that sorts integers by processing individual digits.
Visualization
Details
Analogy
Imagine sorting a list of words alphabetically without comparing them directly. First, you sort all the words into 26 buckets based on their last letter. Then you re-collect them and sort them again into buckets based on their second-to-last letter, and so on, until you reach the first letter. After the final pass, the entire list of words will be perfectly sorted.
Purpose
To sort integers by grouping keys by individual digits which share the same significant position and value. It processes digits from least significant to most significant.
Use Cases
Highly effective for sorting large sets of integers or string keys. Because it's not comparison-based, it can beat O(n log n) sorting algorithms in performance.
Algorithm Steps
find max value in arr
exp = 1
while max / exp > 0:
countingSort(arr, exp)
exp *= 10
function countingSort(arr, exp):
create output and count arrays
count occurrences of digits at exp position
convert count to cumulative count
build output array from right to left
copy output back to arr
Explanation
What's Happening?
Initial unsorted array.
Code Implementation
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_for_radix(arr, exp)
exp *= 10
return arr
def counting_sort_for_radix(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]