Implementation


#include <iostream>
using namespace std;

int getMax(int a[], int n)
{
    int max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] > max)
            max = a[i];
    }
    return max; // maximum element from the array
}

void countSort(int a[], int n) // function to perform counting sort
{
    int output[n + 1];
    int max = getMax(a, n);
    int count[max + 1]; // create count array with size [max+1]

    for (int i = 0; i <= max; ++i)
    {
        count[i] = 0; // Initialize count array with all zeros
    }

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

    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1]; // find cumulative frequency

    /* This loop will find the index of each element of the original array in count array, and
     place the elements in output array*/
    for (int i = n - 1; i >= 0; i--)
    {
        output[count[a[i]] - 1] = a[i];
        count[a[i]]--; // decrease count for same numbers
    }

    for (int i = 0; i < n; i++)
    {
        a[i] = output[i];
    }
}
    // Driver code
    int main()
    {
        int a[] = {31, 11, 42, 7, 30, 11};
        int n = 6;
        countSort(a, n);
        cout << "Sorted array: ";
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
        return 0;
    }

Output


Sorted array: 7 11 11 30 31 42