Counting Sort is a simple and efficient sorting algorithm, especially useful for sorting integers within a known range. Unlike comparison-based sorting algorithms such as quicksort or mergesort, Counting Sort counts the occurrence of each element and then calculates the position of each element in the sorted output. This makes it extremely fast for datasets where the maximum value is not too large compared to the number of elements.
with hands-on learning.
get the skills and confidence to land your next move.
This algorithm is widely used in situations where stability is important or when sorting objects based on integer keys. For Rust programmers, implementing Counting Sort is a great way to practice working with arrays, slices, and basic loops while understanding how non-comparison-based sorting works. Beginners can benefit from seeing how counting frequencies can lead directly to a sorted array without traditional element comparisons.
Program 1: Basic Counting Sort for Small Integers
This program demonstrates the core idea of Counting Sort by sorting a small array of integers.
fn counting_sort(arr: &mut [usize]) {
if arr.is_empty() {
return;
}
let max = *arr.iter().max().unwrap();
let mut count = vec![0; max + 1];
for &num in arr.iter() {
count[num] += 1;
}
let mut index = 0;
for i in 0..=max {
for _ in 0..count[i] {
arr[index] = i;
index += 1;
}
}
}
fn main() {
let mut numbers = [4, 2, 2, 8, 3, 3, 1];
println!("Original array: {:?}", numbers);
counting_sort(&mut numbers);
println!("Sorted array: {:?}", numbers);
}This simple example shows how Counting Sort works by tallying each number’s occurrence and then reconstructing the array in order. Beginners can understand how counting frequencies eliminates the need for traditional comparisons.
Program 2: Counting Sort with Dynamic Maximum Value
This version calculates the maximum value dynamically, making it adaptable to different datasets.
fn counting_sort_dynamic(arr: &mut [usize]) {
if arr.is_empty() {
return;
}
let max_val = *arr.iter().max().unwrap();
let mut count = vec![0; max_val + 1];
for &num in arr.iter() {
count[num] += 1;
}
let mut index = 0;
for i in 0..=max_val {
for _ in 0..count[i] {
arr[index] = i;
index += 1;
}
}
}
fn main() {
let mut numbers = [10, 5, 3, 10, 2, 8, 5];
println!("Original array: {:?}", numbers);
counting_sort_dynamic(&mut numbers);
println!("Sorted array: {:?}", numbers);
}Dynamic maximum calculation allows the algorithm to handle arrays with different ranges efficiently. Beginners see how the algorithm adapts without requiring a fixed maximum value.
Program 3: Counting Sort for Negative and Positive Integers
Counting Sort is extended to handle negative numbers by offsetting indices.
fn counting_sort_with_negatives(arr: &mut [i32]) {
if arr.is_empty() {
return;
}
let min_val = *arr.iter().min().unwrap();
let max_val = *arr.iter().max().unwrap();
let range = (max_val - min_val + 1) as usize;
let mut count = vec![0; range];
for &num in arr.iter() {
count[(num - min_val) as usize] += 1;
}
let mut index = 0;
for i in 0..range {
for _ in 0..count[i] {
arr[index] = i as i32 + min_val;
index += 1;
}
}
}
fn main() {
let mut numbers = [-5, -10, 0, -3, 8, 5, -1];
println!("Original array: {:?}", numbers);
counting_sort_with_negatives(&mut numbers);
println!("Sorted array: {:?}", numbers);
}By handling negatives, Counting Sort becomes more versatile. Beginners learn how offsets can allow non-negative indexing in arrays.
Program 4: Counting Sort with Debug Prints
This program adds debug statements to visualize how Counting Sort counts and rebuilds the array.
fn counting_sort_debug(arr: &mut [usize]) {
if arr.is_empty() {
return;
}
let max_val = *arr.iter().max().unwrap();
let mut count = vec![0; max_val + 1];
for &num in arr.iter() {
count[num] += 1;
println!("Counting {}: {:?}", num, count);
}
let mut index = 0;
for i in 0..=max_val {
for _ in 0..count[i] {
arr[index] = i;
index += 1;
println!("Placing {} at index {}", i, index - 1);
}
}
}
fn main() {
let mut numbers = [4, 2, 2, 8, 3, 3, 1];
println!("Original array: {:?}", numbers);
counting_sort_debug(&mut numbers);
println!("Sorted array: {:?}", numbers);
}Debug output helps beginners understand the step-by-step counting and placement process, clarifying how the algorithm works internally.
Program 5: Recursive Approach for Counting Sort
While Counting Sort is typically iterative, this recursive example shows a different approach to reconstructing the sorted array.
fn counting_sort_recursive(arr: &mut [usize]) {
if arr.is_empty() {
return;
}
let max_val = *arr.iter().max().unwrap();
let mut count = vec![0; max_val + 1];
for &num in arr.iter() {
count[num] += 1;
}
fn fill(arr: &mut [usize], count: &[usize], index: &mut usize, value: usize) {
if value >= count.len() {
return;
}
for _ in 0..count[value] {
arr[*index] = value;
*index += 1;
}
fill(arr, count, index, value + 1);
}
let mut idx = 0;
fill(arr, &count, &mut idx, 0);
}
fn main() {
let mut numbers = [4, 2, 2, 8, 3, 3, 1];
println!("Original array: {:?}", numbers);
counting_sort_recursive(&mut numbers);
println!("Sorted array: {:?}", numbers);
}This recursive approach emphasizes that even simple algorithms can be expressed in multiple ways, giving beginners insight into recursion combined with array processing.
Frequently Asked Questions (FAQ)
Q1: Is Counting Sort stable?
Yes, Counting Sort is a stable algorithm, meaning it preserves the relative order of equal elements.
Q2: Can Counting Sort handle negative numbers?
Yes, by shifting indices to handle negative values, Counting Sort can sort negative and positive integers.
Q3: When should I use Counting Sort?
Counting Sort is ideal for integers within a small range relative to the array size. It’s not suitable for very large ranges.
Q4: How does Counting Sort compare to quicksort?
Counting Sort can be faster for small ranges and is stable, while quicksort is generally faster for large, unsorted arrays but not stable.
Q5: Can Counting Sort be used for floating-point numbers?
Directly no, because Counting Sort relies on integer indices. You would need to map floats to integers first.
Conclusion
Counting Sort in Rust is a great algorithm for beginners to understand non-comparison-based sorting. By exploring simple counting, dynamic ranges, handling negatives, debug outputs, and recursion, learners can grasp both the efficiency and versatility of the algorithm. Practicing these examples helps beginners improve their Rust programming skills, learn array manipulations, and understand how alternative sorting strategies can outperform traditional methods for specific datasets.
