Bucket Sort is a simple and intuitive sorting algorithm that works by dividing an array into several “buckets,” sorting each bucket individually, and then combining them. This approach is especially efficient when the input is uniformly distributed across a known range. Rust programmers benefit from learning Bucket Sort because it introduces practical ways to handle collections, use vectors, and implement basic sorting techniques while keeping the code readable.
with hands-on learning.
get the skills and confidence to land your next move.
Bucket Sort is commonly used in applications like sorting floating-point numbers, handling large datasets with known ranges, and even in computer graphics for histogram calculations. For beginners, implementing Bucket Sort in Rust provides a hands-on experience with loops, vector operations, and iterative sorting, all while demonstrating how dividing a problem into smaller parts can make algorithms more efficient.
Program 1: Basic Bucket Sort for Floating-Point Numbers
This program demonstrates the basic implementation of Bucket Sort for floating-point numbers between 0 and 1.
fn bucket_sort(arr: &mut [f32]) {
let n = arr.len();
if n == 0 {
return;
}
let mut buckets: Vec<Vec<f32>> = vec![Vec::new(); n];
for &num in arr.iter() {
let index = (num * n as f32) as usize;
let idx = if index < n { index } else { n - 1 };
buckets[idx].push(num);
}
for bucket in buckets.iter_mut() {
bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
}
let mut i = 0;
for bucket in buckets {
for num in bucket {
arr[i] = num;
i += 1;
}
}
}
fn main() {
let mut numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68];
println!("Original array: {:?}", numbers);
bucket_sort(&mut numbers);
println!("Sorted array: {:?}", numbers);
}This program introduces beginners to the concept of dividing elements into buckets, sorting each bucket, and combining results. Using vectors makes it easy to handle variable-sized buckets in Rust.
Program 2: Bucket Sort with Debug Statements
This version includes debug prints to show the state of each bucket before and after sorting.
fn bucket_sort_debug(arr: &mut [f32]) {
let n = arr.len();
if n == 0 {
return;
}
let mut buckets: Vec<Vec<f32>> = vec![Vec::new(); n];
for &num in arr.iter() {
let index = (num * n as f32) as usize;
let idx = if index < n { index } else { n - 1 };
buckets[idx].push(num);
}
for (i, bucket) in buckets.iter().enumerate() {
println!("Bucket {} before sort: {:?}", i, bucket);
let mut bucket_sorted = bucket.clone();
bucket_sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
println!("Bucket {} after sort: {:?}", i, bucket_sorted);
}
let mut i = 0;
for bucket in buckets.iter_mut() {
bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
for num in bucket {
arr[i] = *num;
i += 1;
}
}
}
fn main() {
let mut numbers = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47];
println!("Original array: {:?}", numbers);
bucket_sort_debug(&mut numbers);
println!("Sorted array: {:?}", numbers);
}Debug prints help beginners visualize how elements are grouped into buckets and sorted step by step.
Program 3: Bucket Sort for Integers with Range Handling
This program adapts Bucket Sort to handle integers over a known range.
fn bucket_sort_integers(arr: &mut [u32]) {
if arr.is_empty() {
return;
}
let max_val = *arr.iter().max().unwrap();
let n = arr.len();
let mut buckets: Vec<Vec<u32>> = vec![Vec::new(); n];
for &num in arr.iter() {
let index = (num * (n as u32 - 1) / max_val) as usize;
buckets[index].push(num);
}
for bucket in buckets.iter_mut() {
bucket.sort();
}
let mut i = 0;
for bucket in buckets {
for num in bucket {
arr[i] = num;
i += 1;
}
}
}
fn main() {
let mut numbers = [42, 32, 33, 52, 37, 47, 51];
println!("Original array: {:?}", numbers);
bucket_sort_integers(&mut numbers);
println!("Sorted array: {:?}", numbers);
}This demonstrates how Bucket Sort can efficiently handle integer arrays by mapping numbers to buckets based on their relative value.
Program 4: Bucket Sort with Dynamic Buckets Using Vec
Here, we show how dynamic vectors can automatically adjust bucket sizes during sorting.
fn bucket_sort_dynamic(arr: &mut Vec<f32>) {
let n = arr.len();
if n == 0 { return; }
let mut buckets: Vec<Vec<f32>> = vec![Vec::new(); n];
for &num in arr.iter() {
let index = (num * n as f32) as usize;
let idx = if index < n { index } else { n - 1 };
buckets[idx].push(num);
}
for bucket in buckets.iter_mut() {
bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
}
arr.clear();
for bucket in buckets {
arr.extend(bucket);
}
}
fn main() {
let mut numbers = vec![0.91, 0.45, 0.78, 0.12, 0.34, 0.56];
println!("Original vector: {:?}", numbers);
bucket_sort_dynamic(&mut numbers);
println!("Sorted vector: {:?}", numbers);
}Using Vec’s dynamic behavior allows beginners to manage variable-length buckets without worrying about fixed sizes.
Program 5: Bucket Sort with Custom Sorting Function
This program allows a custom sorting function for each bucket.
fn bucket_sort_custom<F>(arr: &mut [f32], compare: F)
where
F: Fn(&f32, &f32) -> std::cmp::Ordering,
{
let n = arr.len();
if n == 0 { return; }
let mut buckets: Vec<Vec<f32>> = vec![Vec::new(); n];
for &num in arr.iter() {
let mut index = (num * n as f32) as usize;
if index >= n { index = n - 1; }
buckets[index].push(num);
}
// Sort each bucket using the comparator
for bucket in buckets.iter_mut() {
bucket.sort_by(&compare);
}
// Flatten buckets into the array
let mut i = 0;
for bucket in buckets {
for num in bucket {
arr[i] = num;
i += 1;
}
}
arr.sort_by(compare);
}
fn main() {
let mut numbers = [0.78, 0.17, 0.39, 0.26];
println!("Original array: {:?}", numbers);
// Descending
bucket_sort_custom(&mut numbers, |a, b| b.partial_cmp(a).unwrap());
println!("Sorted array (descending): {:?}", numbers);
// Ascending
bucket_sort_custom(&mut numbers, |a, b| a.partial_cmp(b).unwrap());
println!("Sorted array (ascending): {:?}", numbers);
}Custom sorting functions give beginners insight into Rust’s flexible closure system and how to modify algorithms for different orderings.
Frequently Asked Questions (FAQ)
Q1: What is Bucket Sort used for?
Bucket Sort is ideal for sorting numbers that are uniformly distributed or fall within a known range, such as floating-point numbers in [0,1).
Q2: Does Bucket Sort work for negative numbers?
Yes, but negative numbers require shifting or mapping to positive values before assigning to buckets.
Q3: How does Bucket Sort differ from Radix Sort?
Bucket Sort distributes elements into buckets and sorts within each bucket, while Radix Sort processes numbers digit by digit.
Q4: Is Bucket Sort stable?
It can be stable depending on the sorting algorithm used for individual buckets.
Q5: Can Bucket Sort handle integers and floats together?
Yes, but careful normalization is needed to map both types into buckets correctly.
Conclusion
Implementing Bucket Sort in Rust is an excellent way for beginners to explore vector operations, loops, and custom sorting functions. From basic floating-point arrays to dynamic vectors and custom comparators, these examples illustrate the flexibility of the algorithm. Practicing Bucket Sort strengthens understanding of distributing data, manipulating collections, and efficiently combining results. Rust’s powerful vector handling and safe memory management make it an ideal language for experimenting with such sorting algorithms.
