Counting Sort Algorithm in DSA C++ - Time & Space Complexity

Time Complexity: Counting Sort Algorithm

O(n + k)

Understanding Time Complexity

We want to understand how the time needed by Counting Sort changes as the input size grows.

Specifically, how does the number of steps grow when sorting more numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void countingSort(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    int count[maxVal + 1] = {0};
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i]-- > 0) {
            arr[index++] = i;
        }
    }
}
    

This code sorts an array of integers by counting how many times each number appears, then rebuilding the sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three loops: one to find the max value, one to count occurrences, and one to rebuild the sorted array.
• How many times: Each loop runs either n times (input size) or maxVal times (range of input values).

How Execution Grows With Input

The time grows with both the number of elements and the range of values.

Input Size (n)	Approx. Operations
10 (maxVal=5)	About 10 + 6 + 10 = 26 steps
100 (maxVal=50)	About 100 + 51 + 100 = 251 steps
1000 (maxVal=500)	About 1000 + 501 + 1000 = 2501 steps

Pattern observation: The steps grow roughly in proportion to n plus the range maxVal.

Final Time Complexity

Time Complexity: O(n + k)

This means the time depends on the number of elements n plus the range of values k.

Common Mistake

[X] Wrong: "Counting Sort always runs in linear time O(n)."

[OK] Correct: The time also depends on the range of input values k. If k is very large compared to n, the algorithm can be slower.

Interview Connect

Knowing how Counting Sort scales helps you choose the right sorting method for different data. This skill shows you understand trade-offs in algorithms.

Self-Check

"What if the input array contains negative numbers? How would the time complexity change?"

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