Counting Sort in C

Before jumping to the counting sort in c example, first, you have to understand sorting, the sorting algorithms, and the need to use sorting algorithms. We require sorting when we need to arrange data in a particular sequence or arrangement, especially when the data is large. Counting sort takes O(n+k) time to sort an array and O(n+k) space to hold the array. It is O(n) in time and space when the number of items to be sorted is not asymptotically different than the number of values those items can take on.

In this article, we will cover all about counting sort (in C) with an example. So, let’s understand the basics of counting sort in C.

What is Counting Sort?

Counting sort is based on keys between 0 to k range. It assumes that n is the number of integers to be sorted and k is the highest value element. It works by counting the number of integers with distinct key values. The counting sort algorithm uses 3 types of array:

Input Array – To store the input data.
Output Array – For storing the sorted data values.
Temporary Array – To store data temporarily.

A Counting Sort Example

To understand the counting sort (in C) technique easily, let's take an example. To keep things simple, we are taking the data in the range of 0 to 9. Input data: 1, 4, 1, 2, 7, 6, 2 1) In step 1, you need to take a count array that stores the count of each unique object in the input. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 2 0 1 0 1 1 0 0 *count shows how many times the indexed number repeats in the input. 2) The next step is to modify the count array such that each element at each index value stores the sum of previous counts. Index: 0 1 2 3 4 5 6 7 8 9 Count: (0) (0+2=2) (2+2=4) (4+0=4) (4+1=5) (5+0=5) (5+1=6) (6+1=7) (7+0=7) (7+0=7) *Here, the count is like this by adding the count of step 1 and step 2 as shown in brackets. The modified count array shows the position of each object in the output sequence. 3) In the final step, write the output of each object from the input sequence followed by decreasing its count by 1 to place the next data at an index 1 smaller than this index. Process the input data: 1, 4, 1, 2, 7, 6, 2 The position of 1 is 2. Put data 1 at index 2 in output. Final Output: 1, 1, 2, 2, 4, 6, 7

Steps in the Counting Sort Algorithm

Create a count array, which is populated by tallying or hashing all the elements in the original array by their frequency i.e. how many times they appear.
Accumulatively, add the values in the populated count array.
Shift over the array by incrementing the index of each value by one.
Iterate over original array translating values using count array. Be sure to increment the count array as you sort.

Counting Sort

Example of Counting Sort in C Programming

// Counting Sort in C program
#include <stdio.h> 
#include <string.h> 
#define RANGE 255 
// The function to sort the given string arr[] in alphabetical order.
void countSort(char arr[]) 
{ 
// It is the output character array to store sorted arr.
char output[strlen(arr)]; 
// It is the count array to store count of individual characters.
int count[RANGE + 1], i; 
memset(count, 0, sizeof(count)); 
// Store count of each character.
for(i = 0; arr[i]; ++i) 
++count[arr[i]]; 
 
// Position of this character in the output array.
for (i = 1; i <= RANGE; ++i) 
count[i] += count[i-1]; 
 
// Build the output character array.
for (i = 0; arr[i]; ++i) 
{ 
output[count[arr[i]]-1] = arr[i]; 
--count[arr[i]]; 
} 
/* 
For Stable algorithm 
for (i = sizeof(arr)-1; i>=0; --i) 
{ 
output[count[arr[i]]-1] = arr[i]; 
--count[arr[i]]; 
} 
For Logic: See implementation
*/
for (i = 0; arr[i]; ++i) 
arr[i] = output[i]; 
} 
// Driver program to test the above function.
int main() 
{ 
char arr[] = "techgeekbuzz";//"applepp"; 
countSort(arr); 
printf("The sorted character array is %sn.", arr); 
return 0; 
}

Output: The sorted character array is techgeekbuzz.

Example of Counting Sort in C++ Programming

#include<bits/stdc++.h>
using namespace std;

void countsort(int arr[], int n, int k)

{
    int output[n];
    int count[k];

    memset(count, 0, sizeof(count));

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

    int commulative = 0;

    for (int i = 0; i < k; i++)
    {
        int oldCount = count[i];
        count[i] = commulative;
        commulative += oldCount;
    }

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

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

int main()
{
    int arr[] = { 1, 5, 4, 3, 2 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 6;

    countsort(arr, n, k);

    for (int i = 0; i < n; i++) {
        cout<<arr[i]<<" ";
    }
    return 0;
}

Output

1 2 3 4 5

Example of Counting Sort in Python Programming

def countsort(arr, k):
    output = [0] * len(arr)
 
    count = [0] * k
 
    for i in arr:
        count[i] = count[i] + 1
 
    cumulative = 0
    for i in range(k):
        oldCount = count[i]
        count[i] = cumulative
        cumulative += oldCount
 
    for i in arr:
        output[count[i]] = i
        count[i] = count[i] + 1
 

    for i in range(len(arr)):
        arr[i] = output[i]
arr = [1, 5, 4, 3, 2]
k = 6
 
countsort(arr, k)
print(arr)

Output

[1, 2, 3, 4, 5]

Advantages

Counting sort is faster than quick sort and merge sort because it runs in O(n) time complexity in any case, which makes it asymptotically faster than other comparison-based sorting techniques.
It is a stable sorting algorithm. This means that counting sort keeps the number with the same value in the output as they were in the input array.
Counting sort is simple to code.
It can be used to sort negative inputs also.
Counting sort is not a comparison-based sorting algorithm. It counts the frequency of each value in the input.

Disadvantages

We can use counting sort only on integers.
Counting sort performs its best when the set of integers to be sorted is not large. It works best for fewer integers .
It is not an in-place sorting technique.
Counting sort requires O(n+k) extra storage to store temporary data values.

Real-Time Applications

If you need a bounded list of small integer values in linear time then counting sort is your best bet. Counting sort is also used to sub-routine in other sorting techniques.

Conclusion

So that was all about counting sort in C. Hopefully, the aforementioned example helped you understand how the integer sorting algorithm works in the C programming language and in general. Lastly, do mention your queries and doubts in the comments section below. We'd be happy to help! People are also reading:

Counting Sort

Table of Content