Counting Sort Algorithm

While learning about sorting techniques, you mostly hear about Bubble Sort, Selection Sort, or Quick Sort. But there is another sorting technique, which is called Counting Sort. This method is especially useful when you are working with integers or elements within a limited range. In this blog, you will learn what the Counting Sort algorithm is, how it works, its time complexity, and how it can be implemented in C, C++, Java, and Python. So let’s get started!

Table of Contents:

What is Counting Sort

Counting Sort is a special type of sorting technique that works based on the range of the input values. Unlike other sorting algorithms that compare elements, the Counting Sort algorithm is used to arrange elements in linear time by using an extra array to keep track of the counts. The main idea of this algorithm is to count the number of times each unique element appears in the array, and then use those counts to put the elements back in the correct order.

The Counting Sort algorithm works well when the range of input elements is small and can be compared to the size of the array. For example, for the input [1, 4, 0, 8, 1, 1], the size of the array is 6 and the range of elements is from 0 to 8.

Working of Counting Sort

Given below is the step-by-step working process of this algorithm:

Step 1: Finding the Maximum Element

In the first step, you need to look through the given array to find the largest element. This value allows you to determine the size of the counting array. In the example given below, the maximum value of the array is 8. Therefore, you have to create a counting array of size 8 + 1 = 9.

Step 2: Create a Count Array

In the second step, you have to make an array (count array) that can hold counts for all the numbers from 0 to the maximum number. You can initialize all the values of the array to zero.

Step 3: Count the Occurrences

In step 3, when you go through the original array, you need to check the numbers one by one. For every number, you have to go to its position in the count array and then increase its value by 1. In this way, the array keeps track of how many times each number appears in the original array. 

Step 4: Modify the Count Array

In step 4, after counting how many times each number appears, you have to change the count array so that each position adds up all the counts before it. This gives you the total number of elements less than or equal to that number. By doing this, you will have an exact idea of where each number should be placed in the sorted array.

Step 5: Build the Output Array

In step 5, you have to use the cumulative count array to find out exactly where each element from the original array should go in the new output array. You have to place the number at the position indicated by the count array. After placing the number, you have to decrease its count by 1 so that if the same number appears again, it goes to the next correct position.

Step 6: Copy Back to Original Array

In the last step, you have to copy the sorted output array back to the original array. This is necessary if you want the original array to hold the sorted values. After this, the array is fully sorted.

Counting Sort Pseudo-code

The pseudo-code for the Counting Sort algorithm is given below for your reference:

countingSort(arr, n)
    maximum <- find the largest element in arr
    Create a count array of size maximum + 1
    Initialize the count array with all 0's

    // Count the frequency of each element
    for i <- 0 to n-1
        count[arr[i]] <- count[arr[i]] + 1  // store count at element’s index

    // Compute cumulative count
    for i <- 1 to maximum
        count[i] <- count[i] + count[i - 1]

    // Place elements into correct position
    for j <- n-1 down to 0
        output[count[arr[j]] - 1] <- arr[j]  // copy element to output
        count[arr[j]] <- count[arr[j]] - 1   // decrease count

    // Copy sorted elements back to original array
    for i <- 0 to n-1
        arr[i] <- output[i]

Explanation

1. Find the maximum element: At first, you have to go through the array to find the largest number. This decides the size of the count array.
2. Create and initialize the count array: After that, a count array of size maximum + 1 is created, and all the values are set to 0.
3. Count the occurrences: Then you have to go through the original array and increase the count for each number in the count array.
4. Make the cumulative sum: Then the current array is updated so that each value shows the total elements ≤ that number. This provides you with the correct position of each element.
5. Build the sorted array: After that, each element is placed in its correct position by using the count array, and then its count is decreased after being placed.

Time Complexity of Counting Sort

By having a good understanding of the counting sort time complexity, you will get to know how fast or efficient your algorithm is. Counting sort is different from comparison-based sorting algorithms, as it does not compare elements; it counts them. The speed of this algorithm depends on the number of elements in the array (n) and the range of values (k).

1. Best Case Complexity

The best-case time complexity applies to any input because this sorting algorithm always counts the elements regardless of what order they are in.

Time complexity: O(n + k)

Here, n is the number of elements in the array, and k is the maximum value in the array.

2. Average Case Complexity

In the average case, Counting Sort goes through all the elements in the array and then processes the count array.

Time Complexity: O(n + k) 

3. Worst Case Complexity

In the worst case, Counting Sort still scans all the elements and builds the count array. Therefore, the time complexity does not change.

Time Complexity: O(n + k)

Boost Your Resume with Real Skills!

Join Our Python Certification Course!

Explore Program

Space Complexity in Counting Sort

Counting Sort requires extra space for the count and output arrays. This means that apart from the original array, you also need additional memory to store frequencies and the final sorted result. If the range of the numbers is very large, then the sorting algorithm uses extra space proportional to O(n + k), where n is the number of elements and k is the range of the elements. This makes it less efficient in terms of space for large ranges. The count array also becomes very big. This makes sorting less efficient.

Space Complexity: O(n + k)

Implementing Counting Sort in Different Languages

Let’s now understand in detail how the counting sort is implemented in different languages.

1. Counting Sort in C

In order to implement counting sort in C, you need to create arrays for counting and output. After that, you have to iterate through the count occurrences, and at last, you have to reconstruct the sorted array. An example code is given below for your reference:

Code:

Output:

Explanation:  The above C code is used to sort an array of integers using the Counting Sort algorithm. This is done by counting the number of times each number appears and then placing them back in order.

2. Counting Sort in C++

Implementation of counting sort in C++ is similar to C. You can use vectors for convenience. The logic of counting frequencies and rebuilding the array remains the same. A sample code is given below for your reference:

Code:

Output:

Explanation:

The above C++ code is used to sort the given numbers in ascending order by using the Counting Sort algorithm. This is done by counting the number of times each number appears and then rearranging them.

3. Counting Sort in Java

For Counting Sort in Java, you can use arrays to store counts and output. The steps remain the same for this sorting algorithm. A sample code is given below for your reference:

Code:

Output:

Explanation: The above Java code is used to sort an array of numbers in ascending order with the help of the Counting Sort algorithm. This is done by counting the frequency of each number and then placing them back in order.

4. Counting Sort in Python

In Python, it is very simple to implement Counting Sort. This is because of the dynamic arrays (lists) in Python. The logic remains the same: count, accumulate, and rebuild the array.

Example:

Output:

Explanation: The above Python code is used to sort a list of numbers in ascending order using the Counting Sort Algorithm. This is done by counting the occurrences of each number and then placing them back in order.

Advantages of Counting Sort Algorithm

1. It is very quick when the numbers have a small range.

2. It keeps the original order of elements unchanged if it is implemented as a stable sort.

3. The algorithm does not compare elements. This makes it an efficient choice for certain datasets.

4. It is easy to understand and code.

5. The time complexity of this sorting algorithm is always O(n + k). Hence, the performance is always consistent.

Disadvantages of Counting Sort Algorithm

1. It needs extra memory for the count and output arrays.

2. If the range of the numbers is large, it becomes inefficient. This is because it requires a large count array.

3. It cannot handle floating-point or string data directly. Unless the values can be mapped to an integer.

4. When the numbers are far apart from each other, it wastes a lot of space.

5. It is only good for specific cases and not all sorting problems.

Applications of Counting Sort Algorithm

1. You can use this sorting algorithm when numbers fall within a small and known range.

2. It works like a subroutine to sort digits in the radix sort algorithm.

3. It also helps to count frequencies and organize data in a quicker way.

4. It is useful in tasks like equalization of a histogram, where the pixel values are counted.

5. It is also useful in ranking scores or grades in an efficient way without any comparisons.

Boost Your Resume with Real Skills!

Join Our Free Python Certification Course!

Explore Program

Conclusion

The Counting Sort algorithm is one of the easiest and fastest sorting techniques when working with numbers in a limited range. It works by counting how many times a number appears and then arranging them in order without making any comparisons. The time complexity of this sorting algorithm remains the same for best, average, and worst cases, O(n + k). You can easily implement Counting Sort in C, C++, Java, and Python as we have shown above. However, it works best only for the data when the range is small and consists of small integers. Overall, it is a great choice for simple and range-based sorting tasks where speed and stability matter.

Upskill today by enrolling in our Java Course, and also prepare for your next interview with our Java Interview Questions.

Counting Sort Algorithm – FAQs