Radix Sort is a fascinating sorting algorithm that organizes numbers digit by digit, starting from the least significant digit to the most significant. Unlike comparison-based algorithms such as Quick Sort or Merge Sort, Radix Sort is a non-comparative algorithm, which makes it extremely efficient for sorting integers, especially when dealing with large datasets. Understanding Radix Sort in Rust helps beginners grasp how algorithms can work on numeric patterns rather than just comparing values directly.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is widely used in applications where speed matters and numbers have a fixed size, such as in digital systems, database indexing, and certain types of data processing. Learning it also teaches Rust programmers how to manipulate arrays, use helper functions effectively, and handle iterations across multiple passes. For beginners, implementing Radix Sort provides both an opportunity to explore Rust’s syntax and an understanding of how efficient sorting can be achieved using clever algorithm design.
Program 1: Basic Radix Sort in Rust
This program demonstrates a simple implementation of Radix Sort for integers using counting sort as a subroutine.
fn counting_sort(arr: &mut [u32], exp: u32) {
let n = arr.len();
let mut output = vec![0; n];
let mut count = vec![0; 10];
for &num in arr.iter() {
count[((num / exp) % 10) as usize] += 1;
}
for i in 1..10 {
count[i] += count[i - 1];
}
for &num in arr.iter().rev() {
output[count[((num / exp) % 10) as usize] - 1] = num;
count[((num / exp) % 10) as usize] -= 1;
}
arr.copy_from_slice(&output);
}
fn radix_sort(arr: &mut [u32]) {
if let Some(&max) = arr.iter().max() {
let mut exp = 1;
while max / exp > 0 {
counting_sort(arr, exp);
exp *= 10;
}
}
}
fn main() {
let mut numbers = [170, 45, 75, 90, 802, 24, 2, 66];
println!("Original array: {:?}", numbers);
radix_sort(&mut numbers);
println!("Sorted array: {:?}", numbers);
}This basic program shows how Radix Sort repeatedly applies counting sort to each digit, progressively sorting the array. Beginners can see how digit extraction works and how multiple passes eventually sort the numbers fully.
Program 2: Radix Sort with Debug Prints
This version adds debug prints to illustrate the intermediate state of the array after sorting each digit.
fn counting_sort_debug(arr: &mut [u32], exp: u32) {
let n = arr.len();
let mut output = vec![0; n];
let mut count = vec![0; 10];
for &num in arr.iter() {
count[((num / exp) % 10) as usize] += 1;
}
for i in 1..10 {
count[i] += count[i - 1];
}
for &num in arr.iter().rev() {
output[count[((num / exp) % 10) as usize] - 1] = num;
count[((num / exp) % 10) as usize] -= 1;
}
arr.copy_from_slice(&output);
println!("After sorting with exp {}: {:?}", exp, arr);
}
fn radix_sort_debug(arr: &mut [u32]) {
if let Some(&max) = arr.iter().max() {
let mut exp = 1;
while max / exp > 0 {
counting_sort_debug(arr, exp);
exp *= 10;
}
}
}
fn main() {
let mut numbers = [329, 457, 657, 839, 436, 720, 355];
println!("Original array: {:?}", numbers);
radix_sort_debug(&mut numbers);
println!("Final sorted array: {:?}", numbers);
}By adding debug prints, beginners can follow the sorting process and see how each digit influences the arrangement of the array.
Program 3: Radix Sort Using Generics
Here, we use Rust generics to allow Radix Sort to work with any integer type that supports arithmetic operations.
fn counting_sort_generic<T: Copy + Into<u32>>(arr: &mut [T], exp: u32) {
let n = arr.len();
let mut output = vec![arr[0]; n];
let mut count = vec![0; 10];
for &num in arr.iter() {
let val: u32 = num.into();
count[((val / exp) % 10) as usize] += 1;
}
for i in 1..10 {
count[i] += count[i - 1];
}
for &num in arr.iter().rev() {
let val: u32 = num.into();
output[count[((val / exp) % 10) as usize] - 1] = num;
count[((val / exp) % 10) as usize] -= 1;
}
arr.copy_from_slice(&output);
}
fn radix_sort_generic<T: Copy + Into<u32>>(arr: &mut [T]) {
if let Some(max) = arr.iter().map(|&x| x.into()).max() {
let mut exp = 1;
while max / exp > 0 {
counting_sort_generic(arr, exp);
exp *= 10;
}
}
}
fn main() {
let mut numbers: [u16; 6] = [170, 45, 75, 90, 802, 24];
println!("Original array: {:?}", numbers);
radix_sort_generic(&mut numbers);
println!("Sorted array: {:?}", numbers);
}Generics make the algorithm flexible and reusable, allowing beginners to experiment with different integer types while maintaining type safety.
Program 4: Radix Sort with Vec Input
This program shows how Radix Sort can be applied to a Vec instead of a fixed array.
fn counting_sort(arr: &mut [u32], exp: u32) {
let n = arr.len();
let mut output = vec![0; n];
let mut count = vec![0; 10];
for &num in arr.iter() {
count[((num / exp) % 10) as usize] += 1;
}
for i in 1..10 {
count[i] += count[i - 1];
}
for &num in arr.iter().rev() {
output[count[((num / exp) % 10) as usize] - 1] = num;
count[((num / exp) % 10) as usize] -= 1;
}
arr.copy_from_slice(&output);
}
fn radix_sort(arr: &mut [u32]) {
if let Some(&max) = arr.iter().max() {
let mut exp = 1;
while max / exp > 0 {
counting_sort(arr, exp);
exp *= 10;
}
}
}
fn main() {
let mut numbers = vec![121, 432, 564, 23, 1, 45, 788];
println!("Original vector: {:?}", numbers);
radix_sort(&mut numbers);
println!("Sorted vector: {:?}", numbers);
}Using Vec demonstrates Rust’s dynamic collections, helping beginners see that Radix Sort works on both fixed arrays and dynamic arrays.
Program 5: Radix Sort with Negative Numbers
Although classic Radix Sort works for positive integers, we can adapt it for negative numbers by separating negatives and positives, sorting individually, and combining results.
fn counting_sort(arr: &mut [u32], exp: u32) {
let n = arr.len();
let mut output = vec![0; n];
let mut count = vec![0; 10];
for &num in arr.iter() {
count[((num / exp) % 10) as usize] += 1;
}
for i in 1..10 {
count[i] += count[i - 1];
}
for &num in arr.iter().rev() {
output[count[((num / exp) % 10) as usize] - 1] = num;
count[((num / exp) % 10) as usize] -= 1;
}
arr.copy_from_slice(&output);
}
fn radix_sort(arr: &mut [u32]) {
if let Some(&max) = arr.iter().max() {
let mut exp = 1;
while max / exp > 0 {
counting_sort(arr, exp);
exp *= 10;
}
}
}
fn radix_sort_with_negatives(arr: &mut [i32]) {
let mut positives: Vec<u32> = arr.iter().filter(|&&x| x >= 0).map(|&x| x as u32).collect();
let mut negatives: Vec<u32> = arr.iter().filter(|&&x| x < 0).map(|&x| (-x) as u32).collect();
radix_sort(&mut positives);
radix_sort(&mut negatives);
negatives.reverse();
for (i, &num) in negatives.iter().enumerate() {
arr[i] = -(num as i32);
}
for (i, &num) in positives.iter().enumerate() {
arr[negatives.len() + i] = num as i32;
}
}
fn main() {
let mut numbers = [170, -45, 75, -90, 802, 24, -2, 66];
println!("Original array: {:?}", numbers);
radix_sort_with_negatives(&mut numbers);
println!("Sorted array: {:?}", numbers);
}This example teaches beginners how to extend algorithms to handle more complex scenarios while keeping code readable.
Frequently Asked Questions (FAQ)
Q1: What is Radix Sort used for?
Radix Sort is ideal for sorting integers quickly, especially when the dataset is large or when sorting fixed-length numeric keys.
Q2: Does Radix Sort work for negative numbers?
Yes, but classic Radix Sort only handles positive integers. For negatives, we need to separate positive and negative numbers and adjust accordingly.
Q3: How is Radix Sort different from Quick Sort?
Radix Sort is non-comparative and sorts based on digits, while Quick Sort compares elements to partition the array. Radix Sort is stable and predictable.
Q4: Can Radix Sort be used with floating-point numbers?
It can, but it requires special handling to convert floats into integers without losing precision.
Q5: Why is Radix Sort fast for large datasets?
Because it sorts numbers digit by digit using linear counting sort, achieving O(nk) complexity, where k is the number of digits, which can be more efficient than comparison-based algorithms for certain ranges.
Conclusion
Rust implementations of Radix Sort provide beginners with a hands-on approach to understanding digit-based sorting and algorithm design. From basic integer arrays to handling negatives and using generics, these programs showcase the flexibility and power of Rust. Practicing Radix Sort helps learners strengthen their understanding of arrays, loops, and helper functions, while also improving problem-solving skills. Exploring variations of Radix Sort encourages beginners to experiment with Rust syntax and develop efficient, robust programs for real-world applications.
