Counting Sort Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Sort on a small array

What is the output of the following Rust code that uses counting sort on the array [4, 2, 2, 8, 3, 3, 1]?

DSA Rust

fn counting_sort(arr: &mut [usize]) {
    let max = *arr.iter().max().unwrap();
    let mut count = vec![0; max + 1];
    for &num in arr.iter() {
        count[num] += 1;
    }
    let mut i = 0;
    for num in 0..=max {
        for _ in 0..count[num] {
            arr[i] = num;
            i += 1;
        }
    }
}

fn main() {
    let mut data = vec![4, 2, 2, 8, 3, 3, 1];
    counting_sort(&mut data);
    println!("{:?}", data);
}

A [1, 2, 2, 3, 3, 4, 8]

B [8, 4, 3, 3, 2, 2, 1]

C [1, 2, 3, 4, 8]

D [1, 1, 2, 2, 3, 3, 4, 8]

💡 Hint

Think about how counting sort counts the frequency of each number and then reconstructs the sorted array.

Counting sort counts how many times each number appears, then writes them back in order. The input has one 1, two 2s, two 3s, one 4, and one 8, so the sorted array is [1, 2, 2, 3, 3, 4, 8].

🧠 Conceptual

intermediate

Counting Sort Stability Property

Which statement best describes the stability property of counting sort?

A Counting sort sorts elements randomly when values are equal.

B Counting sort always reverses the order of equal elements.

C Counting sort does not guarantee any order for equal elements.

D Counting sort preserves the relative order of equal elements.

💡 Hint

Stability means equal elements keep their original order after sorting.

Counting sort is stable because it processes elements in order and places them in the output array preserving their original relative order.

🔧 Debug

advanced

Identify the error in this counting sort implementation

What error will this Rust counting sort code produce when run on the array [3, 1, 2]?

DSA Rust

fn counting_sort(arr: &mut [usize]) {
    let max = *arr.iter().max().unwrap();
    let mut count = vec![0; max];
    for &num in arr.iter() {
        count[num] += 1;
    }
    let mut i = 0;
    for num in 0..max {
        for _ in 0..count[num] {
            arr[i] = num;
            i += 1;
        }
    }
}

fn main() {
    let mut data = vec![3, 1, 2];
    counting_sort(&mut data);
    println!("{:?}", data);
}

A Infinite loop in the for loop

B Index out of bounds panic at count[num] += 1

C No error, outputs [1, 2, 3]

D Compilation error due to missing semicolon

💡 Hint

Check the size of the count vector and the maximum value used as index.

The count vector is created with size max, but max is the largest number in the array. Since indexing is zero-based, count[max] access is out of bounds causing a panic.

🚀 Application

advanced

Counting Sort Usage Scenario

In which scenario is counting sort the best choice compared to other sorting algorithms?

A Sorting a list of floating-point numbers with many decimal places

B Sorting a list of strings alphabetically

C Sorting a large list of integers where the range of values is small

D Sorting a very large list of random integers with a huge range

💡 Hint

Counting sort works best when the range of input values is not much larger than the number of items.

Counting sort is efficient when the range of input values is small compared to the number of elements, as it uses extra space proportional to the range.

📝 Syntax

expert

Correct the syntax to create a counting array in Rust

Which option correctly creates a counting vector for counting sort in Rust for an input array with maximum value max?

A let mut count = vec![0; max + 1];

B let count = vec(0, max + 1);

C let mut count = vec![0] * (max + 1);

D let mut count = vec![0; max];

💡 Hint

Remember the syntax for creating a vector with repeated values in Rust.

Option A uses the correct syntax vec![value; size] to create a vector filled with zeros of length max + 1.

Practice

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

easy

A. Compare each element with every other element to sort

B. Count the occurrences of each element and use counts to place elements in order

C. Divide the array into halves and sort recursively

D. Swap adjacent elements if they are in wrong order repeatedly

Solution

1. Step 1: Understand Counting Sort principle

   Counting sort counts how many times each value appears in the input.

2. Step 2: Use counts to place elements

   These counts help place elements directly in the sorted output without comparisons.

3. Final Answer:

   Count the occurrences of each element and use counts to place elements in order -> Option B

4. Quick Check:

   Counting sort = Counting occurrences and placing [OK]

Hint: Counting sort uses counts, not comparisons, to sort [OK]

Common Mistakes:

• Thinking counting sort compares elements
• Confusing counting sort with quicksort or mergesort
• Assuming counting sort works on all data types

2. Which of the following is the correct Rust syntax to create a vector of zeros with length 5 for counting sort?

easy

A. let counts = vec![0; 5];

B. let counts = vec(0, 5);

C. let counts = [0; 5];

D. let counts = vec::new(5, 0);

Solution

1. Step 1: Recall Rust vector initialization

   In Rust, vec![value; size] creates a vector with repeated values.

2. Step 2: Match syntax to create vector of zeros

   vec![0; 5] creates a vector with five zeros, perfect for counting sort.

3. Final Answer:

   let counts = vec![0; 5]; -> Option A

4. Quick Check:

   vec![0; 5] creates vector of 5 zeros [OK]

Hint: Use vec![value; size] to create repeated elements vector [OK]

Common Mistakes:

• Using parentheses instead of square brackets for vec!
• Confusing array syntax with vector syntax
• Trying to use vec::new with parameters

3. What will be the output of the following Rust code snippet implementing counting sort on array [4, 2, 2, 8, 3, 3, 1]?

fn counting_sort(arr: &[usize]) -> Vec<usize> {
    let max = *arr.iter().max().unwrap();
    let mut counts = vec![0; max + 1];
    for &num in arr {
        counts[num] += 1;
    }
    let mut sorted = Vec::new();
    for (num, &count) in counts.iter().enumerate() {
        for _ in 0..count {
            sorted.push(num);
        }
    }
    sorted
}

fn main() {
    let arr = [4, 2, 2, 8, 3, 3, 1];
    let sorted = counting_sort(&arr);
    println!("{:?}", sorted);
}

medium

A. [0, 1, 2, 3, 4, 8]

B. [8, 4, 3, 3, 2, 2, 1]

C. [1, 3, 2, 4, 8]

D. [1, 2, 2, 3, 3, 4, 8]

Solution

1. Step 1: Count occurrences of each number

   Input array: [4, 2, 2, 8, 3, 3, 1]. Counts: 1->1, 2->2, 3->2, 4->1, 8->1.

2. Step 2: Build sorted vector using counts

   Push each number count times in order: 1, 2, 2, 3, 3, 4, 8.

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option D

4. Quick Check:

   Sorted array = [1, 2, 2, 3, 3, 4, 8] [OK]

Hint: Counting sort output is sorted array with repeated elements [OK]

Common Mistakes:

• Forgetting to repeat elements by their count
• Outputting original array instead of sorted
• Miscounting occurrences of elements

4. Identify the bug in this Rust counting sort code snippet and choose the fix:

fn counting_sort(arr: &[usize]) -> Vec<usize> {
    let max = arr.iter().max().unwrap();
    let mut counts = vec![0; *max];
    for &num in arr {
        counts[num] += 1;
    }
    let mut sorted = Vec::new();
    for (num, &count) in counts.iter().enumerate() {
        for _ in 0..count {
            sorted.push(num);
        }
    }
    sorted
}

medium

A. Change let max = arr.iter().max().unwrap(); to let max = *arr.iter().max().unwrap();

B. Change for &num in arr to for num in arr.iter()

C. Change vec![0; *max] to vec![0; *max + 1]

D. Change sorted.push(num) to sorted.push(count)

Solution

1. Step 1: Check vector size for counts

   Vector size is *max, but max element index is *max, so size must be *max + 1 to include max.

2. Step 2: Fix counts vector size

   Changing to vec![0; *max + 1] prevents out-of-bound errors when counting max element.

3. Final Answer:

   Change vec![0; *max] to vec![0; *max + 1] -> Option C

4. Quick Check:

   Counts vector size = max + 1 [OK]

Hint: Counts vector must cover all indices up to max element [OK]

Common Mistakes:

• Not adding +1 to vector size for max element
• Dereferencing max incorrectly
• Pushing count instead of element in sorted vector

5. You want to sort an array of integers that includes negative numbers using counting sort in Rust. Which approach correctly adapts counting sort for this case?

hard

A. Shift all numbers by adding the absolute value of the minimum negative number before counting

B. Use the original counting sort without changes; it works with negatives

C. Ignore negative numbers and sort only non-negative ones

D. Convert all numbers to positive by multiplying by -1 before sorting

Solution

1. Step 1: Understand counting sort limitation

   Counting sort requires non-negative indices for counts, so negatives cause index errors.

2. Step 2: Shift numbers to non-negative range

   Add absolute value of minimum negative number to all elements to shift them to zero or positive before counting.

3. Step 3: Sort and then shift back

   After sorting, subtract the shift to restore original values in sorted order.

4. Final Answer:

   Shift all numbers by adding the absolute value of the minimum negative number before counting -> Option A

5. Quick Check:

   Shift negatives to non-negative before counting sort [OK]

Hint: Shift negatives to zero or positive before counting sort [OK]

Common Mistakes:

• Trying to use counting sort directly on negatives
• Ignoring negative numbers in input
• Multiplying negatives by -1 changes order incorrectly