Home » C++ programming language

Counting Sort with C++ Example

Counting Sort Algorithm in C++: In this tutorial, we will learn about the counting sort algorithm and the implementation of the counting sort algorithm using the C++ program. By Shubham Singh Rajawat Last updated : August 06, 2023

Counting sort algorithm

The counting sort is a sorting algorithm that is used for sorting according to the given keys. Counting sort is not a comparison sort and it is an integer sorting algorithm. It operates by counting the number of objects that possess distinct key values and applying prefix sum on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum key value and the minimum key value, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. It is often used as a subroutine in radix sort, another sorting algorithm, which can handle larger keys more efficiently. [source]

In short, the counting sort is used for small integers it is an algorithm with a complexity of O(n+k) as worst case where 'n' is the number of elements and k is the greatest number among all the elements .

Example with explanation

Let us understand this with the help of an example:

Here,
n=7 and A[] = {0,1,5,7,8,6,3}

At first, C[] = {0,0,0,0,0,0,0,0,0}

Now we will modify C[]
C[] = {1,1,0,1,0,1,1,1,1}

Now we will modify C[],
so that it contains the last occurrence of any element 
x at C[x]

C[1] = C[0]+c[1], C[2]=C[1]+C[2], ... and so on
C[] = {1,2,2,3,3,4,5,6,7}   /*Index of will start from zero*/

Now we will store the sorted array in B[] by traversing A[] 
and checking the position of that element from C[]

/*Index of A[] and B[] will start from one*/
So first, A[7] = 3
So the position of 3 in B[] is 3 and then we will update C[3] = 2

Next, A[6] = 6
So the position of 6 in B[] is 5 and then we will update C[6] = 4

And this will keep on going until we reach 
the first element then we will get 

our sorted array B[] will be:

B[] = {0,1,3,5,6,7,8}

C++ program to implement counting sort algorithm

#include <iostream>
using namespace std;

int k = 0;

/*Method to sort the array*/
void Counting_Sort(int A[], int B[], int n)
{
    int C[k];
    for (int i = 0; i < k + 1; i++) {
        /*It will initialize the C with zero*/
        C[i] = 0;
    }
    
    for (int j = 1; j <= n; j++) {
        /*It will count the occurence of every element x in A 
		and increment it at position x in C*/
        C[A[j]]++;
    }
    
    for (int i = 1; i <= k; i++) {
        /*It will store the last 
		occurence of the element i */
        C[i] += C[i - 1];
    }
    
    for (int j = n; j >= 1; j--) {
        /*It will place the elements at their 
		respective index*/
        B[C[A[j]]] = A[j];
        /*It will help if an element occurs 
		more than one time*/
        C[A[j]] = C[A[j]] - 1;
    }
}

// Main code
int main()
{
    int n;
    
    cout << "Enter the size of the array :";
    cin >> n;

    /*A stores the elements input by user */
    /*B stores the sorted sequence of elements*/
    int A[n], B[n];

    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        if (A[i] > k) {
            /*It will modify k if an element 
			occurs whose value is greater than k*/
            k = A[i];
        }
    }
    
    Counting_Sort(A, B, n);
    
    /*It will print the sorted sequence on the 
	console*/
    for (int i = 1; i <= n; i++) {
        cout << B[i] << " ";
    }

    cout << endl;
    
    return 0;
}

Output

First Run:
Enter the size of the array :10
12 345 89 100 23 0 18 44 111 1
0 1 12 18 23 44 89 100 111 345

Second Run:
Enter the size of the array :5
999 87 12 90 567
12 87 99 567 999    

Explanation

Method Counting_Sort() contains three arguments A contains the elements entered by user, B array in which sorted elements are stored , n is the size of array A.

First of all we will have to initialize the array C with zero then we will store the frequency of elements in another array C i.e. if the value of an input element is x , we increment C[i](to store the occurrence of each number) then we will modify C[x] so that it will contain the last occurrence of the element x this can be done by storing the sum of C[x] and C[x-1] in C[x].

Now we will traverse the array A from last and find its position from C and that element in B at that address and at last we will modify C so that duplicate element will not end up in the same position in B.