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 frequency of each element

↓

Modify count array to store cumulative counts

↓

Place elements into output array using count array

↓

Copy output array back to input array

↓

Done

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	Count Array State	Output Array State	Input Array State
1	Find max value in arr	N/A	N/A	[4, 2, 2, 8, 3, 3, 1]
2	Create count array of size max+1 (9)	[0, 0, 0, 0, 0, 0, 0, 0, 0]	N/A	[4, 2, 2, 8, 3, 3, 1]
3	Count frequency of each element	[0, 1, 2, 2, 1, 0, 0, 0, 1]	N/A	[4, 2, 2, 8, 3, 3, 1]
4	Modify count array to cumulative counts	[0, 1, 3, 5, 6, 6, 6, 6, 7]	N/A	[4, 2, 2, 8, 3, 3, 1]
5	Place elements into output array (process from right to left)	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[4, 2, 2, 8, 3, 3, 1]
6	Copy output array back to input array	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[1, 2, 2, 3, 3, 4, 8]
7	End of sorting	[0, 0, 1, 3, 5, 6, 6, 6, 6]	[1, 2, 2, 3, 3, 4, 8]	[1, 2, 2, 3, 3, 4, 8]

💡 All elements placed in sorted order, input array updated.

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

Key Moments - 3 Insights

Why do we process the input array from right to left when placing elements into the output array?

Processing from right to left ensures stable sorting by placing duplicates in correct order, as shown in step 5 of the execution_table.

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

Cumulative counts tell the exact position of each element in the output array, as seen in step 4 where 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 indices represent values; negative numbers would cause invalid indexing.

Visual Quiz - 3 Questions

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

A 1

B 3

C 2

D 0

💡 Hint

Check the count array state at step 3 in execution_table, index 3 shows frequency.

At which step does the count array become cumulative?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the count array state changes in execution_table rows for step 4.

If the input array had an extra element '0', how would the count array size change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would double

💡 Hint

Count array size depends on max value + 1, adding 0 does not increase max value.

Concept Snapshot

Counting Sort Algorithm:
- Find max value in input
- Create count array size max+1
- Count frequencies of each element
- Convert count array to cumulative counts
- Place elements in output using count array
- Copy output back to input
- Works only for non-negative integers

Full Transcript

Counting sort works by counting how many times each number appears in the input array. First, it finds the maximum value to know how big the count array should be. Then it creates and initializes the count array with zeros. Next, it counts the frequency of each number in the input. After that, it changes the count array to cumulative counts, which tell where each number should go in the output array. Then it places each element from the input into the output array by looking up positions in the count array, processing from right to left to keep the order stable. Finally, it copies the sorted output back to the input array. This method only works for non-negative integers because the count array uses values as indices.

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 place each element directly into 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 = Count the occurrences of each element and use counts to place elements in order [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 any data type

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

easy

A. int count[9] = {0};

B. int count[10] = {0};

C. int count[11] = {0};

D. int count[] = {0};

Solution

1. Step 1: Determine size of count array

   Input values range from 0 to 9, so we need 10 slots (0 through 9).

2. Step 2: Declare count array with size 10

   Using int count[10] = {0}; initializes all counts to zero for indices 0 to 9.

3. Final Answer:

   int count[10] = {0}; -> 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 9 instead of 10
• Not initializing count array to zero
• Declaring count array without size

3. What is the output of the following C++ code snippet using counting sort on array arr = {4, 2, 2, 8, 3, 3, 1}?

void countingSort(int arr[], int n) {
    int output[n];
    int count[9] = {0};
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
    for (int i = 1; i < 9; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    return 0;
}

medium

A. 2 2 3 3 4 8 1

B. 8 4 3 3 2 2 1

C. 1 2 3 4 8 2 3

D. 1 2 2 3 3 4 8

Solution

1. Step 1: Count frequencies and cumulative counts

   Count array after counting: count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1; cumulative sums give positions.

2. Step 2: Place elements in output using counts

   Elements placed in output array in sorted 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 input array [OK]

Common Mistakes:

• Not using cumulative counts correctly
• Placing elements in wrong order
• Using wrong count array size

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

void countingSort(int arr[], int n) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i <= n; i++)
        count[arr[i]]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

medium

A. Initialize output array with zeros

B. Increase count array size to 11

C. Change loop to for (int i = 0; i < n; i++) in first for loop

D. Change second for loop to start from i = 0

Solution

1. Step 1: Check loop bounds in counting frequencies

   The first for loop uses i <= n, which accesses arr[n] out of bounds (indexing error).

2. Step 2: Fix loop condition to i < n

   Changing to i < n prevents out-of-bounds access and correctly counts frequencies.

3. Final Answer:

   Change loop to for (int i = 0; i < n; i++) in first for loop -> Option C

4. Quick Check:

   Loop bounds must be less than n to avoid errors [OK]

Hint: Loop over array indices from 0 to n-1 [OK]

Common Mistakes:

• Using <= n instead of < n in loops
• Ignoring array out-of-bounds errors
• Changing unrelated loops unnecessarily

5. Given an array arr = {5, 3, 0, 2, 3, 5, 1, 4} with values ranging from 0 to 5, how would you modify the counting sort algorithm to sort this array in descending order?

hard

A. After computing cumulative counts, iterate from highest to lowest index to place elements in output

B. Reverse the input array before sorting with normal counting sort

C. Use a max heap instead of counting sort for descending order

D. Sort normally and then reverse the output array after counting sort completes

Solution

1. Step 1: Understand normal counting sort placement

   Normal counting sort places elements from lowest to highest using cumulative counts.

2. Step 2: Modify placement to iterate from highest to lowest

   To sort descending, iterate counts from max to min and place elements accordingly in output.

3. Final Answer:

   After computing cumulative counts, iterate from highest to lowest index to place elements in output -> Option A

4. Quick Check:

   Reverse iteration in placement = descending sort [OK]

Hint: Reverse placement loop for descending order [OK]

Common Mistakes:

• Just reversing input without changing counting logic
• Using other sorting algorithms instead of modifying counting sort
• Reversing output after sorting without adjusting counts