Counting Sort Algorithm in DSA C - Execution Trace

Concept Flow - Counting Sort Algorithm

Find max value in input 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 input array

↓

Sorting complete

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};
int n = 7;
countingSort(arr, n);

Sorts the array {4, 2, 2, 8, 3, 3, 1} using counting sort.

Execution Table

Step	Operation	Array State	Count Array State	Output Array State	Pointer/Index Changes	Visual State
1	Find max value	[4, 2, 2, 8, 3, 3, 1]	N/A	N/A	max = 8	Input array unchanged
2	Initialize count array with zeros	[4, 2, 2, 8, 3, 3, 1]	[0, 0, 0, 0, 0, 0, 0, 0, 0]	N/A	count array size = 9	Count array all zeros
3	Count occurrences	[4, 2, 2, 8, 3, 3, 1]	[0, 1, 2, 2, 1, 0, 0, 0, 1]	N/A	count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1	Count array updated with frequencies
4	Cumulative count	[4, 2, 2, 8, 3, 3, 1]	[0, 1, 3, 5, 6, 6, 6, 6, 7]	N/A	count[i] = count[i] + count[i-1] for i=1 to 8	Count array stores positions
5	Build output array (process from right to left)	[4, 2, 2, 8, 3, 3, 1]	[0, 1, 3, 5, 6, 6, 6, 6, 7]	[1, 2, 2, 3, 3, 4, 8]	Place 1 at output[count[1]-1=0], decrement count[1]=0 Place 3 at output[count[3]-1=4], decrement count[3]=4 Place 3 at output[count[3]-1=3], decrement count[3]=3 Place 8 at output[count[8]-1=6], decrement count[8]=6 Place 2 at output[count[2]-1=2], decrement count[2]=2 Place 2 at output[count[2]-1=1], decrement count[2]=1 Place 4 at output[count[4]-1=5], decrement count[4]=5	Output array built in sorted order
6	Copy output to input array	[1, 2, 2, 3, 3, 4, 8]	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	arr[i] = output[i] for i=0 to 6	Input array now sorted
7	End	[1, 2, 2, 3, 3, 4, 8]	N/A	N/A	Sorting complete	Final sorted array

💡 All elements placed in output array and copied back, sorting finished

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	N/A	[0, 1, 2, 2, 1, 0, 0, 0, 1]	[0, 1, 3, 5, 6, 6, 6, 6, 7]	[0, 0, 1, 3, 5, 6, 6, 6, 6]	N/A
output	N/A	N/A	N/A	[1, 2, 2, 3, 3, 4, 8]	N/A
max	N/A	8	8	8	8

Key Moments - 3 Insights

Why do we process the input array from right to left when building the output array?

Processing from right to left ensures the sort is stable, meaning equal elements keep their original order. See step 5 in execution_table where elements are placed starting from the end.

Why do we need to modify the count array to store cumulative counts?

Cumulative counts tell us the exact position where each element should go in the output array. Step 4 in execution_table shows how count array changes to cumulative sums.

What happens if the input array contains negative numbers?

Counting sort as shown only works with non-negative integers because count array indexes correspond to element values. Negative numbers would cause invalid indexing.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does the count array change from frequencies to cumulative counts?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Operation' column and 'Count Array State' changes in execution_table

If the input array had an extra element 2 at the end, how would the count of 2 change after step 3?

A It would increase by 1

B It would decrease by 1

C It would stay the same

D It would become zero

💡 Hint

Refer to variable_tracker for count array changes after step 3

Concept Snapshot

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

Full Transcript

Counting Sort Algorithm sorts an array by counting how many times each number appears. First, it finds the maximum value to know the size of the count array. Then it creates and initializes the count array with zeros. Next, it counts the occurrences of each element in the input array. After that, it modifies the count array to store cumulative counts, which represent positions in the output array. Then, it builds the output array by placing elements at the correct positions, processing the input array from right to left to keep the sort stable. Finally, it copies the sorted output back to the input array. This method works well for non-negative integers with a small range.

Practice

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

easy

A. Counting the number of occurrences of each element to sort

B. Comparing each element with every other element

C. Dividing the array into halves and sorting recursively

D. Swapping adjacent elements 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 in order

   Using these counts, it places elements directly into the sorted output.

3. Final Answer:

   Counting the number of occurrences of each element to sort -> Option A

4. Quick Check:

   Counting occurrences = A [OK]

Hint: Counting occurrences helps sort without comparisons [OK]

Common Mistakes:

• Thinking it compares elements like bubble sort
• Confusing with divide and conquer methods
• Assuming it swaps elements repeatedly

2. Which of the following is the correct way to declare the count array in C for counting sort if the maximum value in input is max_val?

easy

A. int count[max_val + 1];

B. int count[max_val];

C. int count[max_val - 1];

D. int count[max_val * 2];

Solution

1. Step 1: Understand array size for counts

   The count array must hold counts for all values from 0 to max_val inclusive, so size is max_val + 1.

2. Step 2: Choose correct declaration

   Declaring int count[max_val + 1]; ensures space for all possible values.

3. Final Answer:

   int count[max_val + 1]; -> Option A

4. Quick Check:

   Count array size = max_val + 1 [OK]

Hint: Count array size must cover all values including max_val [OK]

Common Mistakes:

• Using max_val size misses last element count
• Using max_val - 1 causes out-of-range errors
• Using double size wastes memory unnecessarily

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

medium

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

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

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

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

Solution

1. Step 1: Count occurrences of each element

   1 appears once, 2 appears twice, 3 appears twice, 4 once, 8 once.

2. Step 2: Place elements in sorted order using counts

   Sorted array is [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

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

4. Quick Check:

   Sorted array = C [OK]

Hint: Count then output in order for sorted array [OK]

Common Mistakes:

• Confusing input order with output order
• Forgetting to repeat elements by their counts
• Mixing up counts and positions

4. Given the following code snippet for counting sort, what is the error?

int count[5] = {0};
int arr[6] = {1, 3, 4, 2, 3, 0};
for (int i = 0; i < 6; i++) {
    count[arr[i]]++;
}
for (int i = 0; i <= 5; i++) {
    printf("%d ", count[i]);
}

medium

A. Incrementing count[arr[i]] is wrong

B. Count array not initialized to zero

C. Array arr size is incorrect

D. Loop accessing count array goes out of bounds

Solution

1. Step 1: Check count array size and loop range

   Count array size is 5 (indices 0 to 4), but loop runs i from 0 to 5 inclusive, accessing count[5] which is out of bounds.

2. Step 2: Identify out-of-bounds access

   Accessing count[5] causes undefined behavior or error.

3. Final Answer:

   Loop accessing count array goes out of bounds -> Option D

4. Quick Check:

   Loop index > count size = D [OK]

Hint: Check array size vs loop limits carefully [OK]

Common Mistakes:

• Ignoring array size when looping
• Assuming initialization fixes out-of-bounds
• Confusing arr size with count size

5. You want to sort an array containing negative and positive integers using counting sort. Which modification is necessary?

hard

A. Use the array as is because counting sort handles negatives naturally

B. Sort only positive numbers and ignore negatives

C. Shift all numbers by adding the absolute value of the minimum element before sorting

D. Use bubble sort instead

Solution

1. Step 1: Understand counting sort limitation

   Counting sort works only with non-negative integers because it uses array indices as counts.

2. Step 2: Adjust negative values for indexing

   Shift all numbers by adding the absolute value of the minimum element to make all values non-negative before counting.

3. Final Answer:

   Shift all numbers by adding the absolute value of the minimum element before sorting -> Option C

4. Quick Check:

   Shift negatives to non-negative = B [OK]

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

Common Mistakes:

• Trying to count negatives directly
• Ignoring negative values in input
• Switching to other sorts unnecessarily