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]
Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]
Output array: [1, 2, 2, 3, 3, 4, 8]

Dry Run Walkthrough

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

Goal: Sort the list in ascending order using counting sort

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

Input: [4, 2, 2, 8, 3, 3, 1]
Max value: 8

Why: We need to know how big the count array should be to cover all values

Step 2: Create count array of size max+1 and initialize with zeros

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

Why: Count array holds how many times each number appears

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

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

Why: We record how many times each number occurs

Step 4: Modify count array to hold cumulative counts

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

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

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

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

Why: We build the sorted array by placing elements at correct positions

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

void countingSort(int arr[], int n) {
    int i;
    if (n == 0) return; // Handle empty array
    // Find max value
    int max = arr[0];
    for (i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // Create count array
    int *count = (int *)calloc(max + 1, sizeof(int));

    // Count frequencies
    for (i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Cumulative count
    for (i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    int *output = (int *)malloc(n * sizeof(int));

    // Build output array
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy to original array
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

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++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" ");
    }
    printf("\n");
    return 0;
}

for (i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } }

Find maximum value to size count array

for (i = 0; i < n; i++) { count[arr[i]]++; }

Count frequency of each number

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

Transform count array to cumulative counts

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

Place elements in output array in sorted order

for (i = 0; i < n; i++) { arr[i] = output[i]; }

Copy sorted output back to original array

Output

1 2 2 3 3 4 8

Complexity Analysis

Time: O(n + k) because we count frequencies and then build output, where n is input size and k is max value

Space: O(n + k) because we use count and output arrays proportional to input size and max value

vs Alternative: Unlike comparison sorts (O(n log n)), counting sort is faster for small ranges but uses extra space

Edge Cases

Empty array

No sorting needed, function handles gracefully

DSA C

int n = sizeof(arr) / sizeof(arr[0]); (main) - no elements means loops skip; countingSort returns immediately

Array with all identical elements

Count array counts all in one bucket, output is same as input

DSA C

for (i = 0; i < n; i++) { count[arr[i]]++; }

Array with single element

Sorted array is same single element

DSA C

for (i = 1; i < n; i++) { if (arr[i] > max) max = arr[i]; } (handles n=1)

When to Use This Pattern

When you need to sort integers with a small range quickly and without comparisons, use counting sort because it counts occurrences to sort in linear time.

Common Mistakes

Mistake: Not using cumulative counts, leading to incorrect positions in output
Fix: Add cumulative sum step to count array before placing elements

Mistake: Placing elements in output array from start to end, causing unstable sort
Fix: Place elements from end to start to maintain stability

Summary

Counting sort sorts numbers by counting how many times each appears and placing them accordingly.

Use it when sorting integers with a limited range for fast, non-comparison sorting.

The key insight is using counts and cumulative sums to find exact positions without comparing elements.

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