This C++ program demonstrates the Counting Sort algorithm, which sorts an array of non-negative integers by counting the occurrences of each element. The implementation includes functions for inputting and printing arrays to facilitate testing.

counting-sort.cpp

#include <iostream>
using namespace std;

void countSort(int a[], int n)
{
    int max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (max < a[i])
        {
            max = a[i];
        }
    }

    int *count = new int[max + 1]();

    for (int i = 0; i < n; i++)
    {
        count[a[i]]++;
    }

    for (int i = 1; i < max + 1; i++)
    {
        count[i] += count[i - 1];
    }

    int *output = new int[n];

    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];
    }
}

void inputArray(int a[], int n)
{
    cout << "Enter " << n << " elements: ";
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
}

void printArray(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main()
{
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int *a = new int[n];

    inputArray(a, n);

    cout << "Original array: ";
    printArray(a, n);

    countSort(a, n);

    cout << "After Sorting: ";
    printArray(a, n);

    delete[] a;
    return 0;
}