Radix Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

Start with least significant digit

↓

Place numbers into buckets by current digit

↓

Collect numbers from buckets in order

↓

Move to next more significant digit

↓

Repeat until all digits processed

↓

Sorted array

Radix sort processes numbers digit by digit from least to most significant, grouping by digit and collecting until fully sorted.

Execution Sample

DSA Rust

fn radix_sort(arr: &mut [u32]) {
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    let mut output = vec![0; arr.len()];
    while max / exp > 0 {
        // Counting sort by digit
    }
}

This code sorts an array of unsigned integers by processing digits from least to most significant.

Execution Table

Step	Operation	Digit Place (exp)	Buckets (0-9)	Array State After Collection	Notes
1	Find max number	-	-	-	Max number found: 802
2	Process digit	1 (units)	[170, 90, 802, 2, 24, 45, 75, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	Buckets by units digit, collected in order
3	Process digit	10 (tens)	[802, 2, 24, 45, 66, 170, 75, 90]	[802, 2, 24, 45, 66, 170, 75, 90]	Buckets by tens digit, collected in order
4	Process digit	100 (hundreds)	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]	Buckets by hundreds digit, collected in order
5	Check next digit	1000	-	-	max/exp = 802/1000 = 0, stop sorting
6	Final sorted array	-	-	[2, 24, 45, 66, 75, 90, 170, 802]	Sorting complete

💡 When max/exp becomes 0, all digits processed and array is sorted.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[170, 45, 75, 90, 802, 24, 2, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	[802, 2, 24, 45, 66, 170, 75, 90]	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]
max	802	802	802	802	802
exp	1	10	100	1000	1000
buckets	[]	[170, 90, 802, 2, 24, 45, 75, 66]	[802, 2, 24, 45, 66, 170, 75, 90]	[2, 24, 45, 66, 75, 90, 170, 802]	[]

Key Moments - 3 Insights

Why do we start sorting from the least significant digit (units place)?

Because radix sort relies on stable sorting by each digit starting from the least significant to preserve the order of previous digits, as shown in steps 2 to 4 in the execution_table.

What happens if the max number has fewer digits than others?

Digits beyond the max number's length are treated as zero, so those numbers go into the zero bucket, ensuring correct order as seen in step 4 where exp=100 processes hundreds digit.

Why do we stop when max/exp becomes zero?

Because it means all digit places have been processed, no more significant digits remain, as explained in step 5 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the array state after collecting from buckets?

A [170, 90, 802, 2, 24, 45, 75, 66]

B [802, 2, 24, 45, 66, 170, 75, 90]

C [2, 24, 45, 66, 75, 90, 170, 802]

D [170, 45, 75, 90, 802, 24, 2, 66]

💡 Hint

Check the 'Array State After Collection' column for Step 2 in execution_table.

At which step does the sorting process stop because max/exp is zero?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Notes' column in execution_table where max/exp calculation is mentioned.

If the max number was 9999 instead of 802, how would the variable 'exp' change in variable_tracker?

A It would stop at 1000 as before

B It would go up to 10000 before stopping

C It would only use exp=1

D It would not change at all

💡 Hint

Refer to the 'exp' row in variable_tracker and the stopping condition in execution_table Step 5.

Concept Snapshot

Radix Sort Algorithm:
- Sorts numbers digit by digit from least to most significant
- Uses buckets (0-9) for each digit place
- Collects numbers from buckets after each digit pass
- Stops when all digit places processed (max/exp == 0)
- Stable and efficient for fixed digit length numbers

Full Transcript

Radix sort works by sorting numbers starting from the least significant digit (units place) and moving to more significant digits (tens, hundreds, etc.). First, it finds the maximum number to know how many digits to process. Then, for each digit place, it places numbers into buckets based on that digit, collects them back in order, and moves to the next digit. This repeats until all digits are processed, resulting in a sorted array. The process is stable and efficient for numbers with fixed digit lengths.

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Sort numbers by swapping adjacent elements repeatedly

B. Sort numbers by comparing each pair directly

C. Sort numbers by dividing them into two halves recursively

D. Sort numbers digit by digit starting from the least significant digit

Solution

1. Step 1: Understand Radix Sort approach

   Radix sort sorts numbers by processing each digit separately, starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, radix sort uses digit positions to sort without direct element comparisons.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option D

4. Quick Check:

   Radix sort = digit-by-digit sorting [OK]

Hint: Radix sort processes digits from right to left [OK]

Common Mistakes:

• Thinking radix sort compares elements directly
• Assuming it sorts by dividing arrays recursively
• Confusing it with bubble or quick sort methods

2. Which of the following Rust code snippets correctly initializes a vector to hold buckets for digits 0 to 9 in radix sort?

easy

A. let mut buckets: Vec = vec![Vec::new(); 10];

B. let buckets = Vec::with_capacity(10);

C. let buckets: Vec<i32> = vec![0; 10];

D. let mut buckets = vec![0; 10];

Solution

1. Step 1: Understand bucket structure needed

   Radix sort uses buckets as vectors of vectors to hold numbers for each digit (0-9).

2. Step 2: Check Rust syntax for initializing vector of vectors

   Using vec![Vec::new(); 10] creates 10 empty vectors, one for each digit bucket.

3. Final Answer:

   let mut buckets: Vec = vec![Vec::new(); 10]; -> Option A

4. Quick Check:

   Vector of vectors for buckets = let mut buckets: Vec = vec![Vec::new(); 10]; [OK]

Hint: Buckets need vectors inside a vector, not just integers [OK]

Common Mistakes:

• Using Vec<i32> instead of Vec for buckets
• Using with_capacity without initializing inner vectors
• Initializing buckets as integers instead of vectors

3. What will be the output of the following Rust code snippet implementing one pass of radix sort on the least significant digit?

let arr = vec![170, 45, 75, 90, 802, 24, 2, 66];
let mut buckets: Vec = vec![Vec::new(); 10];
for &num in &arr {
    let digit = num % 10;
    buckets[digit as usize].push(num);
}
let mut result = Vec::new();
for bucket in buckets {
    for num in bucket {
        result.push(num);
    }
}
println!("{:?}", result);

medium

A. [2, 802, 24, 45, 75, 66, 170, 90]

B. [170, 90, 802, 2, 24, 45, 75, 66]

C. [170, 802, 2, 24, 45, 75, 90, 66]

D. [802, 2, 24, 45, 75, 66, 170, 90]

Solution

1. Step 1: Calculate least significant digit for each number

   Digits: 170%10=0, 45%10=5, 75%10=5, 90%10=0, 802%10=2, 24%10=4, 2%10=2, 66%10=6.

2. Step 2: Place numbers in buckets and flatten

   Buckets: 0->[170,90], 2->[802,2], 4->[24], 5->[45,75], 6->[66]. Flattening in order: [170, 90, 802, 2, 24, 45, 75, 66].

3. Final Answer:

   [170, 90, 802, 2, 24, 45, 75, 66] -> Option B

4. Quick Check:

   Sorted by least digit = [170, 90, 802, 2, 24, 45, 75, 66] [OK]

Hint: Check digit % 10 and group accordingly [OK]

Common Mistakes:

• Mixing up digit extraction with division
• Not preserving order within buckets
• Incorrectly flattening buckets

4. Identify the bug in this Rust code snippet for one pass of radix sort and choose the fix:

let arr = vec![170, 45, 75];
let mut buckets: Vec = vec![Vec::new(); 10];
for num in arr {
    let digit = num / 10 % 10;
    buckets[digit].push(num);
}

medium

A. Change buckets[digit] to buckets[digit as usize]

B. Change num / 10 % 10 to num % 10

C. Initialize buckets with vec![0; 10] instead of vectors

D. Use for &num in &arr instead of for num in arr

Solution

1. Step 1: Identify type mismatch in indexing

   Variable digit is an integer but Rust requires usize for vector indexing.

2. Step 2: Fix by casting digit to usize

   Use buckets[digit as usize] to correctly index the vector.

3. Final Answer:

   Change buckets[digit] to buckets[digit as usize] -> Option A

4. Quick Check:

   Vector index must be usize = Change buckets[digit] to buckets[digit as usize] [OK]

Hint: Vector indices in Rust must be usize type [OK]

Common Mistakes:

• Using integer directly as vector index without casting
• Changing digit calculation unnecessarily
• Incorrect bucket initialization

5. Given the Rust function below that performs radix sort on a vector of positive integers, what will be the final sorted vector?

fn radix_sort(mut arr: Vec<i32>) -> Vec<i32> {
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    while max / exp > 0 {
        let mut buckets: Vec = vec![Vec::new(); 10];
        for &num in &arr {
            let digit = (num / exp) % 10;
            buckets[digit as usize].push(num);
        }
        arr.clear();
        for bucket in buckets {
            for num in bucket {
                arr.push(num);
            }
        }
        exp *= 10;
    }
    arr
}

let input = vec![329, 457, 657, 839, 436, 720, 355];
let sorted = radix_sort(input);
println!("{:?}", sorted);

hard

A. [329, 436, 355, 457, 657, 720, 839]

B. [839, 720, 657, 457, 436, 355, 329]

C. [329, 355, 436, 457, 657, 720, 839]

D. [355, 329, 436, 457, 657, 720, 839]

Solution

1. Step 1: Understand the radix sort passes

   The function sorts by digits starting from least significant (units), then tens, then hundreds until max digit processed.

2. Step 2: Trace sorting steps on input

   After all passes, the vector is sorted ascending: [329, 355, 436, 457, 657, 720, 839].

3. Final Answer:

   [329, 355, 436, 457, 657, 720, 839] -> Option C

4. Quick Check:

   Radix sort final output = sorted ascending [OK]

Hint: Radix sort outputs fully sorted list ascending [OK]

Common Mistakes:

• Confusing order as descending
• Missing clearing array before collecting buckets
• Not multiplying exp by 10 each iteration