Radix Sort Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Radix Sort on a small array

What is the output of the following Rust code that implements Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

DSA Rust

fn counting_sort(arr: &mut [u32], exp: u32) {
    let n = arr.len();
    let mut output = vec![0u32; n];
    let mut count = vec![0usize; 10];

    for &num in arr.iter() {
        let index = (num / exp) % 10;
        count[index as usize] += 1;
    }

    for i in 1..10 {
        count[i] += count[i - 1];
    }

    for &num in arr.iter().rev() {
        let index = (num / exp) % 10;
        output[count[index as usize] - 1] = num;
        count[index as usize] -= 1;
    }

    for i in 0..n {
        arr[i] = output[i];
    }
}

fn radix_sort(arr: &mut [u32]) {
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    while max / exp > 0 {
        counting_sort(arr, exp);
        exp *= 10;
    }
}

fn main() {
    let mut arr = vec![170, 45, 75, 90, 802, 24, 2, 66];
    radix_sort(&mut arr);
    println!("{:?}", arr);
}

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

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

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

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

💡 Hint

Radix sort sorts numbers digit by digit starting from the least significant digit.

Radix sort processes digits from least significant to most significant using counting sort as a subroutine. The final sorted array is in ascending order.

🧠 Conceptual

intermediate

Number of passes in Radix Sort

Given an array of unsigned integers where the maximum number is 9999, how many passes (iterations over digits) will the Radix Sort algorithm perform?

A 4

B 5

C 3

D 10

💡 Hint

Count the number of digits in the maximum number.

Radix sort performs one pass per digit. Since 9999 has 4 digits, it will perform 4 passes.

🔧 Debug

advanced

Identify the bug causing incorrect sorting

The following Rust code attempts to implement Radix Sort but produces incorrect output. What is the bug?

DSA Rust

fn counting_sort(arr: &mut [u32], exp: u32) {
    let n = arr.len();
    let mut output = vec![0u32; n];
    let mut count = vec![0usize; 10];

    for &num in arr.iter() {
        let index = (num % exp) / 10;
        count[index as usize] += 1;
    }

    for i in 1..10 {
        count[i] += count[i - 1];
    }

    for &num in arr.iter().rev() {
        let index = (num % exp) / 10;
        output[count[index as usize] - 1] = num;
        count[index as usize] -= 1;
    }

    for i in 0..n {
        arr[i] = output[i];
    }
}

fn radix_sort(arr: &mut [u32]) {
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    while max / exp > 0 {
        counting_sort(arr, exp);
        exp *= 10;
    }
}

A The digit extraction uses (num % exp) / 10 instead of (num / exp) % 10

B The count array size should be 256 instead of 10

C The output vector is not initialized with the correct size

D The loop for updating count array should start from 0 instead of 1

💡 Hint

Check how digits are extracted for sorting.

The expression (num % exp) / 10 does not correctly extract the digit at the current exponent. The correct expression is (num / exp) % 10.

🚀 Application

advanced

Radix Sort on strings of digits

Which option correctly describes how Radix Sort can be adapted to sort an array of strings representing numbers with equal length, e.g. ["170", "045", "075", "090"]?

A Convert strings to integers and apply normal Radix Sort on integers

B Sort the strings from leftmost character to rightmost using counting sort on each character

C Sort the strings from rightmost character to leftmost using counting sort on each character

D Use quicksort instead because Radix Sort cannot sort strings

💡 Hint

Radix Sort processes digits from least significant to most significant.

Radix Sort can sort fixed-length strings by sorting characters from right to left using counting sort at each position.

🧠 Conceptual

expert

Time complexity of Radix Sort with base 10

Given n numbers each with d digits, what is the time complexity of Radix Sort using base 10 counting sort for each digit?

A O(n^2) due to nested loops

B O(d * (n + 10)) which simplifies to O(d * n)

C O(d * n^2) because counting sort is quadratic

D O(n log n) because of digit comparisons

💡 Hint

Counting sort runs in O(n + k) where k is the range of digits (10 here).

Radix Sort runs counting sort d times. Each counting sort is O(n + 10) = O(n). So total is O(d * n).

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