C Program for Counting Sort with Example and Explanation

A C program for counting sort uses an array to count occurrences of each number and then outputs the sorted array by printing numbers based on their counts; the main steps include counting frequencies, accumulating counts, and placing elements in order.

Examples

Input4 2 2 8 3 3 1

Output1 2 2 3 3 4 8

Input5 4 3 2 1

Output1 2 3 4 5

Input7 7 7 7 7

Output7 7 7 7 7

How to Think About It

To sort numbers using counting sort, first find the highest number to know the size of the counting array. Then count how many times each number appears. After that, use these counts to place numbers in the correct order by printing each number as many times as it appeared.

Algorithm

1

Read the input array and find the maximum value.

2

Create a count array of size max+1 and initialize all to zero.

3

Count the frequency of each element in the input array.

4

Modify the count array to store the cumulative counts.

5

Use the count array to place elements in the sorted output array.

6

Print the sorted output array.

Code

c

#include <stdio.h>

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;

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

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[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++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Output

1 2 2 3 3 4 8 

Dry Run

Let's trace the array {4, 2, 2, 8, 3, 3, 1} through the counting sort code.

1

Find max value

Max value found is 8.

2

Initialize count array

Count array of size 9 initialized to all zeros.

3

Count frequencies

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

4

Place elements in sorted order

Output array filled as: 1, 2, 2, 3, 3, 4, 8

Number	Count after counting
0	0
1	1
2	2
3	2
4	1
5	0
6	0
7	0
8	1

Why This Works

Step 1: Counting frequencies

The code counts how many times each number appears using the count array, so it knows the quantity of each number.

Step 2: Rebuilding sorted array

It then rebuilds the sorted array by placing each number as many times as counted, ensuring the output is sorted.

Alternative Approaches

Using cumulative counts for stable sort

c

#include <stdio.h>
#include <string.h>

void countingSortStable(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    int count[max + 1];
    memset(count, 0, sizeof(count));
    int output[n];

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

    for (int i = 1; i <= max; 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]);

    countingSortStable(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

This method keeps the original order of equal elements (stable) but uses extra space for output.

Using sorting library function

c

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Using built-in sort is simpler but not counting sort; it works for all data but may be slower for small integer ranges.

Complexity: O(n + k) time, O(k) space

Time Complexity

Counting sort runs in O(n + k) where n is the number of elements and k is the range of input values. Counting frequencies and outputting sorted array dominate the time.

Space Complexity

It uses O(k) extra space for the count array, where k is the maximum value in the input.

Which Approach is Fastest?

Counting sort is fastest for small ranges of integers compared to comparison-based sorts like quicksort, which are O(n log n).

Approach	Time	Space	Best For
Counting Sort (basic)	O(n + k)	O(k)	Small integer ranges, fast sorting
Counting Sort (stable)	O(n + k)	O(n + k)	Stable sorting with extra space
Library qsort	O(n log n)	O(log n)	General sorting, any data type