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)
{
    int max = getMax(a, n);
    int count[100] ={0}, output[100];
    for (int i = 0; i < n; i++)
    {
        count[a[i]]++;
    }
    for (int i = 1; i <= max; i++)
    {
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--)
    {
        output[--count[a[i]]] = a[i];
    }
    for (int i = 0; i < n; i++)
    {
        a[i] = output[i];
    }
}
// Driver code
int main()
{
    // int arr[] = {31, 11, 42, 7, 30, 11};
    int arr[] = {1,2,4,3,0,2,1,7,1,4,3,0};
    int n = 12;
    countSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Output


Sorted array: 0 0 1 1 1 2 2 3 3 4 4 7