Counting Sort: Complete Guide

What is Counting Sort?

Counting sort is a linear sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array (auxiliary is just a fancy word for helper), and then by iterating through this array the original array is sorted.

When to prefer Counting Sort?

Counting sort is preferred when the range of elements is smaller than the number of elements. In simple words, we could say that counting sort is preferred when many elements are repeated in the given array.

Pseudocode of Counting Sort

 function countingSort(arr, n):
    // Step 1: Find the maximum element in the array
    maxElement = arr[0]
    for i from 1 to n-1:
        if arr[i] > maxElement:
            maxElement = arr[i]

    // Step 2: Create a count array with size maxElement + 1, initialized to 0
    count = array of size (maxElement + 1) initialized to 0

    // Step 3: Store the count of each element
    for i from 0 to n-1:
        count[arr[i]] = count[arr[i]] + 1

    // Step 4: Store the sorted elements back into the original array
    index = 0
    for i from 0 to maxElement:
        while count[i] > 0:
            arr[index] = i
            index = index + 1
            count[i] = count[i] - 1

C++ Code for Counting Sort


void countingSort(int arr[], int n)
{
    // Find the maximum element in the array
    int maxElement = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > maxElement)
        {
            maxElement = arr[i];
        }
    }

    // Create a count array to store the count of each unique element
    int *count = new int[maxElement + 1];
    for (int i = 0; i < maxElement + 1; i++)
    {
        count[i] = 0;
    }

    // Store the count of each element
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
    }

    // Store the sorted elements back into the original array
    int index = 0;
    for (int i = 0; i <= maxElement; i++)
    {
        while (count[i] > 0)
        {
            arr[index] = i;
            index++;
            count[i]--;
        }
    }

    delete[] count;
}

Working of the code using an example

Let's assume we have the following array.
```
    {2,4,6,2,5,6,2,5,7,2,4,3,2}
```
First, we find the maximum number in the array by iterating through the whole array and store it in a variable called maxElement which in this case is 7.
Now we create a new array named count and initialize its size to maxElement + 1 to store the elements count from 0 to maxElement.(As the indexing starts from 0).
We initialize the whole count array with 0 specifying that occurrence of each element at the moment is zero.
Then we iterate through the whole array using a for loop. The loop body says to go to the arr[i] which in first iteration is 2 so it goes to count[2] and increments its value from 0 to 1 and in this way the loop continues till the last element.
The count array looks like this after we have iterated through the original array.
```
   {0,0,5,1,2,2,2,1}
```
The count array shows that there are:

0 occurrences of 0.

0 occurrences of 1.

5 occurrences of 2.

1 occurrence of 3.

2 occurrences of 4.

2 occurrences of 5.

2 occurrences of 6.

1 occurrence of 7.
Now the final step is to iterate through the count array and sort the original array. For this we use a for loop and inside this for loop using while loop we specify the condition that implement the body only when the value in count array is greater than zero i.e. there is any occurrence of any element.
Let me just also quickly explain the loop body. For the first iteration count[i] i.e. count[0] is not greater than zero so it does nothing. Same for count[1] then for count[2] the value is 5 which is greater than zero so now what it does is it goes to arr[index] (index is initialized to 0 before the start of loop) and places the value 2 in arr[0]. Index is incremented by 1 and count[i] is decremented by 1 so now value of count[2] is 4 which is still greater than zero. It again places 2 in the original array till count[2] becomes zero which means no more 2's are left. Then it goes to count[3] and follows this process. In this way the whole count array is iterated, and the original array is sorted.

Time complexity of counting sort

Time complexity of the above function is O(n+k) where n is the number of elements and k is the range of elements.

Real life applications of counting sort

Counting sort is used where counting the frequencies of elements is required like in data analysis for creating histograms or frequency distribution of categorical data.
Counting sort can be used to handle large datasets where the elements fall within a small range.
Counting sort is often used as a subroutine in Radix sort which is another sorting algorithm.

Limitations of Counting sort

Counting sort works only for integers. It cannot be used for sorting of floating-point numbers.
Due to constraints Counting sort is not suitable for all types of data.

This post covers everything you need to know about Counting Sort. If you still have any queries, feel free to ask away—I’m more than happy to help. Your questions and thoughts are always appreciated. Don’t forget to follow this space for more informative tech blogs and updates.

Mastering Counting Sort: A Comprehensive Guide

Table of contents