Counting Sort Algorithm in DSA C# - 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 C#

int[] arr = {4, 2, 2, 8, 3, 3, 1};
CountingSort(arr);
// Sorted arr: 1, 2, 2, 3, 3, 4, 8

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

Execution Table

Step	Operation	Array State	Count Array State	Output Array State	Notes
1	Find max value	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,0,0,0,0,0]	[]	Max value is 8
2	Initialize count array	[4, 2, 2, 8, 3, 3, 1]	[0,0,0,0,0,0,0,0,0]	[]	Count array size 9 (0 to 8)
3	Count occurrences	[4, 2, 2, 8, 3, 3, 1]	[0,1,2,2,1,0,0,0,1]	[]	Count of each number recorded
4	Cumulative count	[4, 2, 2, 8, 3, 3, 1]	[0,1,3,5,6,6,6,6,7]	[]	Count array updated to cumulative counts
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]	Placed elements in output using counts
6	Copy output to original	[1, 2, 2, 3, 3, 4, 8]	[0,1,3,5,6,6,6,6,7]	[1,2,2,3,3,4,8]	Original array updated with sorted values
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]	Sorting complete

💡 All elements placed in sorted order, algorithm ends

Variable Tracker

Variable	Start	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]	[1, 2, 2, 3, 3, 4, 8]
count	[]	[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	[]	[]	[]	[1,2,2,3,3,4,8]	[1,2,2,3,3,4,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 max value, so size max+1 covers all possible values (see Step 2 in execution_table).

Why do we change the count array to cumulative counts?

Cumulative counts tell us the exact position where each number should go in the output array (see Step 4 in execution_table).

Why do we build the output array by iterating the original array backwards?

Iterating backwards ensures stable sorting, preserving the order of equal elements (see Step 5 in execution_table).

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Count Array State' column at Step 3 for the value at index 3.

At which step does the count array become cumulative?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Operation' column and find when 'Cumulative count' happens.

If the input array had an extra 5, how would the count array change after Step 3?

A Count at index 5 would increase by 1

B Count at index 5 would decrease by 1

C Count at index 8 would increase by 1

D No change in count array

💡 Hint

Count array tracks occurrences of each number, so adding a 5 increases count at index 5 (see Step 3).

Concept Snapshot

Counting Sort Algorithm:
- Find max value in array
- Create count array sized max+1
- Count occurrences of each element
- Convert count array to cumulative counts
- Build output array using counts
- Copy output back to original array
- Stable and efficient for small range integers

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 original array. After that, it changes the count array to cumulative counts, which helps to place each element in the correct position in the output array. The output array is built by placing elements according to these counts, iterating the original array backwards to keep the order stable. Finally, the sorted output array is copied back to the original array. This method is efficient for sorting integers within a small range.

Practice

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

easy

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

B. Compare each element with every other element to sort

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 to directly place elements in the sorted output without comparisons.

3. Final Answer:

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

4. Quick Check:

   Counting occurrences = A [OK]

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

Common Mistakes:

• Thinking counting sort compares elements
• Confusing counting sort with merge sort
• Assuming counting sort works on all data types

2. Which of the following is the correct way to declare the count array for counting sort in C# if the input range is from 0 to 9?

easy

A. int[] count = new int[0];

B. int[] count = new int[10];

C. int[] count = new int[11];

D. int count = new int[9];

Solution

1. Step 1: Determine size of count array

   For range 0 to 9, we need 10 slots to count each number.

2. Step 2: Correct C# syntax for array declaration

   Use int[] count = new int[10]; to create an array of size 10.

3. Final Answer:

   int[] count = new int[10]; -> Option B

4. Quick Check:

   Array size = max value + 1 = 10 [OK]

Hint: Count array size = max element value + 1 [OK]

Common Mistakes:

• Using size less than max value + 1
• Declaring count as single int instead of array
• Using incorrect array size causing index errors

3. What will be the output of the following C# code snippet using counting sort on array int[] arr = {4, 2, 2, 8, 3, 3, 1}?

int max = 8;
int[] count = new int[max + 1];
int[] output = new int[arr.Length];

// Count occurrences
foreach (int num in arr) count[num]++;

// Modify count array
for (int i = 1; i <= max; i++) count[i] += count[i - 1];

// Build output
for (int i = arr.Length - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
}

// Print output
foreach (int num in output) Console.Write(num + " ");

medium

A. 1 2 2 3 3 4 8

B. 8 4 3 3 2 2 1

C. 1 3 2 2 3 4 8

D. 2 2 3 3 4 8 1

Solution

1. Step 1: Count occurrences of each number

   Count array after counting: [0,1,2,2,1,0,0,0,1]

2. Step 2: Modify count array to cumulative counts

   Cumulative count: [0,1,3,5,6,6,6,6,7]

3. Step 3: Place elements in output using counts

   Placing elements from right to left gives sorted array: 1 2 2 3 3 4 8

4. Final Answer:

   1 2 2 3 3 4 8 -> Option A

5. Quick Check:

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

Hint: Use cumulative counts to place elements from right [OK]

Common Mistakes:

• Not using cumulative counts before placing elements
• Placing elements from left to right causing wrong order
• Off-by-one errors in indexing output

4. Identify the error in this counting sort code snippet and choose the correct fix:

int max = 5;
int[] count = new int[max];
int[] arr = {1, 4, 3, 2, 5};

foreach (int num in arr) {
    count[num]++;
}

medium

A. Initialize count array with zeros explicitly

B. Change foreach loop to for loop

C. Change count array size to max + 1 to avoid index out of range

D. No error, code is correct

Solution

1. Step 1: Analyze count array size

   Count array size is 5, but max value is 5, so index 5 is out of range.

2. Step 2: Fix by increasing count array size

   Count array should be size max + 1 = 6 to include index 5 safely.

3. Final Answer:

   Change count array size to max + 1 to avoid index out of range -> Option C

4. Quick Check:

   Array size = max + 1 to cover all indices [OK]

Hint: Count array size must be max element + 1 [OK]

Common Mistakes:

• Using count array size equal to max value only
• Ignoring index out of range exceptions
• Assuming default array size is enough

5. You have an array int[] arr = {5, 3, 0, 2, 3, 5, 1, 4} and want to sort it using counting sort. However, the array may contain negative numbers in future. How should you modify the counting sort algorithm to handle negative numbers correctly?

hard

A. Sort negative and positive numbers separately and then merge

B. Ignore negative numbers as counting sort only works for positive numbers

C. Use a dictionary instead of an array for counts

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

Solution

1. Step 1: Identify problem with negative numbers

   Counting sort uses array indices as counts, negative indices are invalid.

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

   Add absolute value of minimum negative number to all elements to make them non-negative.

3. Step 3: Apply counting sort on shifted values

   Sort shifted values, then shift back to original values after sorting.

4. Final Answer:

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

5. Quick Check:

   Shift negatives to zero or above before counting [OK]

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

Common Mistakes:

• Trying to use negative indices in count array
• Ignoring negative values in input
• Using dictionary without sorting logic