Counting Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Counting Sort Algorithm

Find max value in array

↓

Create count array of size max+1

↓

Initialize count array with zeros

↓

Count occurrences of each element

↓

Modify count array to store cumulative counts

↓

Build output array using count array

↓

Copy output array back to original array

↓

Sorted array ready

Counting sort counts how many times each number appears, then uses that to place numbers in order.

Execution Sample

DSA Rust

let arr = [4, 2, 2, 8, 3, 3, 1];
// Counting sort steps
// Output sorted array

Sorts the array by counting occurrences and placing elements in order.

Execution Table

Step	Operation	Array State	Count Array State	Output Array State	Pointer Changes	Visual State
1	Find max value	[4, 2, 2, 8, 3, 3, 1]	N/A	N/A	max=8	[4, 2, 2, 8, 3, 3, 1]
2	Create count array	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,0,0,0,0,0]	N/A	count size=9	[4, 2, 2, 8, 3, 3, 1]
3	Count occurrences	[4, 2, 2, 8, 3, 3, 1]	[0,1,2,2,1,0,0,0,1]	N/A	count updated	[4, 2, 2, 8, 3, 3, 1]
4	Cumulative count	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	N/A	count cumulative	[4, 2, 2, 8, 3, 3, 1]
5	Build output array	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	[1,2,2,3,3,4,8]	output filled	[1, 2, 2, 3, 3, 4, 8]
6	Copy output to original	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	[1,2,2,3,3,4,8]	arr updated	[1, 2, 2, 3, 3, 4, 8]
7	End	[1, 2, 2, 3, 3, 4, 8]	[0,1,3,5,6,6,6,6,7]	[1,2,2,3,3,4,8]	sorted	[1, 2, 2, 3, 3, 4, 8]

💡 All elements placed in output array, original array updated with sorted values.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 5	Final
arr	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[4, 2, 2, 8, 3, 3, 1]	[1, 2, 2, 3, 3, 4, 8]
count	N/A	N/A	[0,1,2,2,1,0,0,0,1]	[0,1,3,5,6,6,6,6,7]	[0,1,3,5,6,6,6,6,7]	[0,1,3,5,6,6,6,6,7]
output	N/A	N/A	N/A	N/A	[1,2,2,3,3,4,8]	[1,2,2,3,3,4,8]
max	N/A	8	8	8	8	8

Key Moments - 3 Insights

Why do we create the count array with size max+1?

Because the count array needs to hold counts for every number from 0 up to the maximum value found in the input array, as shown in step 2 of the execution_table.

Why do we modify the count array to cumulative counts?

Cumulative counts tell us the exact position where each element should go in the output array, as seen in step 4 and used in step 5 of the execution_table.

Why do we copy the output array back to the original array?

Because counting sort builds a separate output array, and to reflect the sorted order in the original array, we copy it back, as shown in step 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the count of number 3?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Count Array State' column at step 3 in the execution_table.

At which step does the count array become cumulative?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for the step where the count array values increase cumulatively in the execution_table.

If the input array had a maximum value of 5 instead of 8, how would the count array size change?

A It would be size 8

B It would be size 5

C It would be size 6

D It would be size 9

💡 Hint

Count array size is max value + 1, see step 2 in execution_table.

Concept Snapshot

Counting Sort Algorithm:
- Find max value in array
- Create count array of size max+1
- Count occurrences of each element
- Convert count array to cumulative counts
- Build output array using counts
- Copy output back to original array
- Result: sorted array in O(n+k) time

Full Transcript

Counting sort works by first finding the maximum value in the array to know the size of the count array. Then it creates a count array initialized with zeros. Next, it counts how many times each number appears in the input array. After that, it changes the count array to hold cumulative counts, which help place elements in the correct order. Then it builds the output array by placing elements at positions indicated by the count array. Finally, it copies the sorted output back to the original array. This process sorts the array efficiently when the range of input values is not too large.

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