Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
3.
Solution Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Approach for Negative Elements
4.1.
Input
4.2.
Output
4.3.
Explanation
4.4.
Algorithm
4.5.
Implementation in C++
4.5.1.
Output
4.6.
Implementation in Java
4.6.1.
Output
5.
Frequently Asked Questions
5.1.
What is the usage of the counting sort algorithm?
5.2.
What is the disadvantage of counting sort?
5.3.
What is the difference between counting sort and bucket sort?
5.4.
Which is the fastest sorting technique?
5.5.
Is counting sort better than quick sort?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Counting Sort

Author Reet Maggo
0 upvote

Introduction

Hey, Ninjas! One of the essential steps in preparation for interviews is learning sorting algorithms. Sorting is one of the crucial topics in data structure and algorithms. It is used to order the items specifically, and many other algorithms require sorting to function efficiently. There are many sorting algorithms like the bubble sortquick sortmerge sort, counting sort, etc.

Title image

This blog will discuss counting sort working, implementation, and its examples. Before diving into the solution, let’s discuss the problem statement again.

Problem Statement

We are given an unsorted array containing non-negative elements. The main task is to sort the given array using the counting sort algorithm.

Input

Total Number of Elements (N) = 9

Array elements = [ 1, 3, 2, 3, 4, 6, 4, 1, 3 ]

Output

After applying the counting sort algorithm, our array looks like this-

Output image

Solution Approach

Counting sort is an integer sorting algorithm, which sorts elements in an array according to small positive integer keys. The method organizes an array by counting how many times each distinct array element appears. It is not a comparison-based algorithm as it doesn’t compare any two elements; instead, it hashes the value with their corresponding value and uses the position array to find the position of the current element in the sorted array.
 

Two operations that take place in the counting sort are as follows:

  1. Count the number of unique elements in the array.
  2. Determine each element's location or the index at which it will appear in the sorted array.

Algorithm

  1. Find the input array's maximum element and store it in the variable ‘max_element.’
     
  2. The ‘count’ array is declared with a size of (max_element - min_element + 1)and initialized with all elements' initial count being 0; the count is incremented every time the number at the index occurs in the array.
     
  3. The ‘position’ array is declared and initialized with all elements' initial count being 0, which will store the position of each element in the sorted array.
     
  4. The ‘position’ array is updated by taking the cumulative sums of the ‘count’ array.
     
  5. The ‘count’ array is updated for positions by taking the sum of previous elements and storing it as the position for the sorted array.
     
  6. Elements are put into the sorted array using a for loop, and the function is finally called for sorting a given array.
     
  7. Finally, the sorted array is displayed as the output and the input array to compare the two.

Dry Run

First, we need to store the count of all distinct elements in the initial array. For that, the maximum value in the array is stored in the variable ‘max_element’, and a new array of this length is created. (The size of the new array will be 6.)

Dry run image 1

Now with the length of the array being equal to the largest value stored, the count of the biggest element present in the initial array will be stored at the maximum index of the new array (the count of element ‘6’ in the initial array is stored at index 6 in the new array). 
 

The ‘count’ array is updated according to the frequency of elements occurring in the initial array.
 

Our ‘count’ array looks like this-

Dry run image 2

However, we need to store each element's count and the last element's count to make the final sorted array. 

This is stored in the ‘position array’ because the position of the next element depends on the number of times its previous element is repeated. 

E.g - (There are two ‘1’s in the array, so after sorting, ‘2’ will be placed after two ‘1’s, i.e., the second index, and goes on).

Dry run image 3

To calculate the position of elements for the final sorted array, the value at each element's ‘position’ index is stored at the corresponding index as the sum of the number stored at the previous index. 

For example, the position of the element ‘2’ will be 2 + 1 in the sorted array. Similarly, the position of element ‘3’ will be 3 + 3 in the final array.

Dry run image 4

Finally, we start with the last element of the initial array (3), go to that particular index (index 3) in the position array, and decrement the element at that index(6 is decremented to 5). 

The resulting number (5) would be the index in the final array where the particular element will be placed. 
 

After that, we have also decreased the position[3] value as the first 3 is placed, and then the next 3 is placed on the index = 4 and this process goes on till all the elements are placed.
 

Similarly, performing this operation for all indexes, our final sorted array looks like this-

Dry run image 5

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

// Function for performing counting sort
void counting_sort(vector <int> &arr){
    
    // Array size
    int N=arr.size();

    int max_element = 0;
    // Finding a maximum element of the array
    for (int i = 0; i < N; i++){
        max_element = max(max_element, arr[i]);
    }


    // Initialising the count array
    vector <int> count(max_element+1,0);
    for (int i = 0; i < N; i++){
        count[arr[i]]++;
    }
    
    // Initialising the position array
    vector <int>position(max_element+1,0);
    
    // Changing the count array for positions
    for (int i = 0; i <= max_element; i++){
        
        position[i] = count[i];
        if(i){
            position[i] += position[i-1];
        }
    }
    
    // Array for storing the final sorted array
    vector <int> sorted (N);

    for (int i = N - 1; i >= 0; i--){
        
        position[arr[i]] -= 1;
        sorted[position[arr[i]]] = arr[i];
    }
    
    for(int i = 0; i < N ;i++){
        arr[i]=sorted[i];
    }
}

int main(){
    
    // The total number of elements in the array
    int N = 9;
    
    // Elements of the array
    vector <int> arr = { 1, 3, 2, 3, 4, 6, 4, 1, 3 };
    
    cout<<"Initial array \n";
    for(auto i:arr){
        cout<<i<<" ";
    }
    cout<<"\n\n";
    
    // Calling counting sort the sort the array
    counting_sort(arr);

    cout<<"Array after sorting \n";
    for(auto i:arr){
        cout<<i<<" ";
    }
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output

O3

Implementation in Java

public class MyClass {
    
    // Function for performing counting sort
    static void counting_sort(int arr[]){
        
        // Array size
        int N=arr.length;
    
        int max_element = 0;
        // Finding maximum element of the array
        for (int i = 0; i < N; i++){
            max_element = Math.max(max_element, arr[i]);
        }
        
        // Initialising the count array
        int p=max_element+1;
        int count[];
        count = new int [p];
        for (int i = 0; i <= max_element; i++){
            count[i]=0;
        }
        
        // Storing count of each element
        for (int i = 0; i < N; i++){
            count[arr[i]]++;
        }
        
        // Initialising the position array
        int position[];
        position = new int [max_element+1];
        for (int i = 0; i <= max_element; i++){
            position[i]=0;
        }
        
        // Changing the count array for positions
        for (int i = 0; i <= max_element; i++){
            
            position[i] = count[i];
            if(i>0){
                position[i] += position[i-1];
            }
        }
        
        // Array for storing the final sorted array
        int sorted[];
        sorted = new int [N];
        
        for (int i = N - 1; i >= 0; i--){
            
            position[arr[i]] -= 1;
            sorted[position[arr[i]]] = arr[i];
        }
        
        for(int i = 0; i < N ;i++){
            arr[i]=sorted[i];
        }
    }
    
    // Driver Function
    public static void main(String args[]) {
        
        // Number of days
        int N = 9;
        
        // Declaration of prices vector
        int arr[] = { 1, 3, 2, 3, 4, 6, 4, 1, 3 };
        
        System.out.println("Initial Array");
        for(int i = 0 ;i < N; i++){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        System.out.println();
        System.out.println();
        
        // Function call to perform counting sort
        counting_sort(arr);
        
        System.out.println("Final Sorted Array");
        for(int i = 0 ;i < N; i++){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        
    }
}
You can also try this code with Online Java Compiler
Run Code


Output

Output image 3

Time Complexity

The time complexity of the counting sort algorithm is O(N + K), ‘N’ being the number of elements in the array and ‘K’ being the range of elements in it.
 

Explanation: The count ‘K’ array is read on the output pass, and a new array is written with ‘N’ elements. So there are ‘N’ reads and K writes (to zero the counts), then ‘N’ writes and 'K' reads for (2 N + 2 K) operations, but since constant two is ignored, the time complexity comes out to be O (N + K).
 

Note: If the range of input values does not exceed the number of values to be sorted, counting sort is most effective.

Space Complexity

For an array with the maximum element being ‘K’ and ‘N’ being the size of the array, the space complexity is O(K + N) for counting sort.
 

Explanation:  Two arrays of size N and K are declared corresponding to ‘sorted’ and ‘count’ & ‘position’ arrays which yield an overall space of O(N + 2*K) where we can ignore the constant 2, which forms O(N + K) space complexity.
 

Note: A larger range of elements gives larger space complexity. Therefore the Counting array is not ideal for a large range of integers. 

Approach for Negative Elements

In the above-mentioned approach, the maximum number of the given elements is extracted and we initialize the count array according to the maximum element. In this approach, along with calculating the maximum element, we will also calculate the minimum number of the array and initialize the count array accordingly. We will shift the value of each element by a value equal to the minimum element of the array. 

Input

Total Number of Elements (N) = 9

Array elements = [ -1, -3, 2, 3, 4, 6, 4, 1, 3 ]

Output

After applying the counting sort algorithm, our array looks like this-

[-3, -1, 1, 2, 3, 3, 4, 4, 6]

Explanation

While applying the counting sort algorithm, we will shift all the elements to the right by a value equal to the minimum element of the array. In the above example, the minimum element is equal to -3. Hence, all the elements will have the value as mentioned below:

  • -3 will have a value of 0 in the count array.
  • -1 will have a value of 2 in the count array.
  • 1 will have a value of 4 in the count array.
  • 2 will have a value of 5 in the count array.
  • 3 will have a value of 6 in the count array.
  • 4 will have a value of 7 in the count array.
  • 6 will have a value of 9 in the count array.
     

We can observe that all the elements of the array are shifted towards the positive side by a value equal to the minimum element of the array.

Algorithm

  1. Find the input array's maximum element and store it in the variable ‘max_element.’
     
  2. Find the input array's minimum element and store it in the variable ‘min_element.’
     
  3. The ‘count’ array is declared and initialized with all elements' initial count being 0; the count is incremented every time the number at the index occurs in the array.
     
  4. The ‘position’ array is declared and initialized with all elements' initial count being 0, which will store the position of each element in the sorted array.
     
  5. The ‘position’ array is updated by taking the cumulative sums of the ‘count’ array.
     
  6. The ‘count’ array is updated for positions by taking the sum of previous elements and storing it as the position for the sorted array.
     
  7. Elements are put into the sorted array using a for loop, and the function is finally called for sorting a given array.
     
  8. Finally, The sorted array is displayed as the output and the input array to compare the two.

Implementation in C++

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

// Function for performing counting sort
void counting_sort(vector <int> &arr){
    
    // Array size
    int N=arr.size();

    int max_element = 0;
    // Finding a maximum element of the array
    for (int i = 0; i < N; i++){
        max_element = max(max_element, arr[i]);
    }
    
    int min_element = INT_MAX;
    // Finding a maximum element of the array
    for(int i=0; i < N; i++){
        min_element = min(min_element, arr[i]);
    }

    // Initialising the count array
    vector <int> count(max_element - min_element + 1,0);
    for (int i = 0; i < N; i++){
        count[arr[i] - min_element]++;
    }
    
    // Initialising the position array
    vector <int>position(max_element - min_element + 1,0);
    
    // Changing the count array for positions
    for (int i = 0; i <= max_element - min_element; i++){
        
        position[i] = count[i];
        if(i){
            position[i] += position[i-1];
        }
    }
    
    // Array for storing the final sorted array
    vector <int> sorted (N);

    for (int i = N - 1; i >= 0; i--){
        
        position[arr[i] - min_element] -= 1;
        sorted[position[arr[i] - min_element]] = arr[i];
    }
    
    for(int i = 0; i < N ;i++){
        arr[i]=sorted[i];
    }
}

int main(){
    
    // The total number of elements in the array
    int N = 9;
    
    // Elements of the array
    vector <int> arr = { -1, -3, 2, 3, 4, 6, 4, 1, 3 };
    
    cout<<"Initial array \n";
    for(auto i:arr){
        cout<<i<<" ";
    }
    cout<<"\n\n";
    
    // Calling counting sort the sort the array
    counting_sort(arr);


    cout<<"Array after sorting \n";
    for(auto i:arr){
        cout<<i<<" ";
    }
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output

Output image 4

Implementation in Java

public class MyClass {
    
    // Function for performing counting sort
    static void counting_sort(int arr[]){
        
        // Array size
        int N=arr.length;
    
        int max_element = 0;
        // Finding maximum element of the array
        for (int i = 0; i < N; i++){
            max_element = Math.max(max_element, arr[i]);
        }
        
        int min_element = Integer.MAX_VALUE;
        // Finding a maximum element of the array
        for(int i=0; i < N; i++){
            min_element = Math.min(min_element, arr[i]);
        }
        
        // Initialising the count array
        int p=max_element - min_element + 1;
        int count[];
        count = new int [p+1];
        for (int i = 0; i <= p; i++){
            count[i]=0;
        }
        
        // Storing count of each element
        for (int i = 0; i < N; i++){
            count[arr[i] - min_element]++;
        }
        
        // Initialising the position array
        int position[];
        position = new int [p+1];
        for (int i = 0; i <= p; i++){
            position[i]=0;
        }
        
        // Changing the count array for positions
        for (int i = 0; i <= p; i++){
            
            position[i] = count[i];
            if(i>0){
                position[i] += position[i-1];
            }
        }
        
        // Array for storing the final sorted array
        int sorted[];
        sorted = new int [N];
        
        for (int i = N - 1; i >= 0; i--){
            
            position[arr[i] - min_element] -= 1;
            sorted[position[arr[i] - min_element]] = arr[i];
        }
        
        for(int i = 0; i < N ;i++){
            arr[i]=sorted[i];
        }
    }
    
    // Driver Function
    public static void main(String args[]) {
        
        // Number of days
        int N = 9;
        
        // Declaration of prices vector
        int arr[] = { -1, -3, 2, 3, 4, 6, 4, 1, 3 };
        
        System.out.println("Initial Array");
        for(int i = 0 ;i < N; i++){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        System.out.println();
        System.out.println();
        
        // Function call to perform counting sort
        counting_sort(arr);
        
        System.out.println("Final Sorted Array");
        for(int i = 0 ;i < N; i++){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
        
    }
}
You can also try this code with Online Java Compiler
Run Code


Output

Output image 4

 

Must Read Difference between ArrayList and LinkedList

Frequently Asked Questions

What is the usage of the counting sort algorithm?

The counting sort algorithm efficiently sorts arrays with non-negative integer keys, such as a list of positive integers, with keys just the value of the integer or a list of words having keys assigned to them by some scheme.

What is the disadvantage of counting sort?

The use of counting sort is only limited to arrays with integer elements because an array of frequencies cannot be constructed otherwise.

What is the difference between counting sort and bucket sort?

Bucket sort involves linked lists, dynamic arrays, or a large amount of pre-allocated memory, while count sort stores a single number, i.e., the count of items per bucket.

Which is the fastest sorting technique?

Quicksort is considered the quickest sorting algorithm because its time complexity is O( N log N) in the best and almost average case scenarios, and in the worst case, it goes up to O (N ^ 2). Thus, it has the upper hand in most cases.

Is counting sort better than quick sort?

Counting sort has better time complexity. However, it has worse space complexity. The better option depends on whether memory or CPU consumption is prioritized.

Moreover, counting sort might be computationally superior but can only be used for small integer values. Hence it cannot replace quicksort in all conditions.

Conclusion

Sorting algorithms are important as searching elements in a sorted array becomes easier than in an unsorted array. Overall, the time complexity of searching for an element is significantly reduced, which plays an essential role in programming. Some real-life applications of sorting algorithms are a contact list on your phone, a music playlist on your phone, and so on.
 

In this blog, we discussed the topic of the counting sort algorithm and the working of the algorithm. We also implemented the algorithm in two different languages C++ and Java. Sorting algorithms are also an essential topic in view of interview preparations and placement. It is, therefore, imperative to become an expert with sorting algorithms, understand what goes underneath the hood, and where you can apply your learnings.
 

Recommended Reading:

Do check out the Interview guide for Product Based Companies, as well as some of the popular interview problems asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
 

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!

Live masterclass