Counting Sort Algorithm in DSA C++

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by counting how many balls of each color you have, then lining them up color by color based on those counts.

Input array: 4 -> 2 -> 2 -> 8 -> 3 -> 3 -> 1 -> null
Count array: [0,0,0,0,0,0,0,0,0]
Output array: [ , , , , , , , ]

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Find the maximum value to know count array size

Input: 4 -> 2 -> 2 -> 8 -> 3 -> 3 -> 1 -> null
Max value: 8

Why: We need to know the range of numbers to create the count array

Step 2: Initialize count array with zeros for each number from 0 to max

Count array: [0,0,0,0,0,0,0,0,0]

Why: Prepare to count occurrences of each number

Step 3: Count each number's frequency in the input array

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

Why: We know how many times each number appears

Step 4: Modify count array to store cumulative counts

Count array cumulative: [0,1,3,5,6,6,6,6,7]

Why: Cumulative counts tell the position of each number in output

Step 5: Place each element from input into output array using count array

Output array after placing elements: [1,2,2,3,3,4,8]

Why: Build the sorted array by placing elements at correct positions

Result:

Sorted array: 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 8 -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return; // handle empty array

    int max_val = arr[0];
    for (int num : arr) {
        if (num > max_val) max_val = num; // find max value
    }

    vector<int> count(max_val + 1, 0); // count array
    for (int num : arr) {
        count[num]++; // count frequency
    }

    for (int i = 1; i <= max_val; i++) {
        count[i] += count[i - 1]; // cumulative count
    }

    vector<int> output(arr.size());
    for (int i = (int)arr.size() - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i]; // place element
        count[arr[i]]--; // decrease count
    }

    for (int i = 0; i < (int)arr.size(); i++) {
        arr[i] = output[i]; // copy back to original
    }
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for (int num : arr) {
        cout << num << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

for (int num : arr) { if (num > max_val) max_val = num; }

find the maximum value to size count array

for (int num : arr) { count[num]++; }

count frequency of each number

for (int i = 1; i <= max_val; i++) { count[i] += count[i - 1]; }

compute cumulative counts for positions

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

place elements in output array in sorted order

for (int i = 0; i < (int)arr.size(); i++) { arr[i] = output[i]; }

copy sorted output back to original array

Output

1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 8 -> null

Complexity Analysis

Time: O(n + k) because we count frequencies in O(n) and process count array of size k (max value)

Space: O(n + k) because we use output array of size n and count array of size k

vs Alternative: Unlike comparison sorts (O(n log n)), counting sort is faster when range k is not much larger than n

Edge Cases

empty array

function returns immediately without error

DSA C++

if (arr.empty()) return;

array with one element

array remains unchanged as it is already sorted

DSA C++

for (int num : arr) { if (num > max_val) max_val = num; }

array with all elements the same

count array counts one number, output array copies original

DSA C++

count[num]++;

When to Use This Pattern

When you need to sort integers with a known small range quickly, use counting sort because it avoids comparisons and sorts in linear time.

Common Mistakes

Mistake: Not using cumulative counts to find correct positions, leading to incorrect output order
Fix: Compute cumulative counts before placing elements to know exact positions

Mistake: Placing elements in output array from start to end, which breaks stability
Fix: Place elements from end to start to maintain stable sorting

Summary

Counting sort sorts numbers by counting their occurrences and placing them in order using these counts.

Use counting sort when sorting integers with a limited range efficiently.

The key insight is using cumulative counts to directly place elements without comparisons.

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