count_sort.cpp

#include <bits/stdc++.h>
using namespace std;

void display(int array[], int size)
{
    for (int i = 1; i <= size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int getMax(int array[], int size)
{
    int max = array[1];
    for (int i = 2; i <= size; i++)
    {
        if (array[i] > max)
            max = array[i];
    }
    return max;
}

void countSort(int array[], int size)
{
    int output[size + 1]; 

    int k=array[1];
    for(int i=0;i<size;i++){
        k=max(k,array[i]);
    }
    //int max = getMax(array, size);

    int count[k + 1]; // create count array (max+1 number of elements)
    for (int i = 0; i <= k; i++)
        count[i] = 0; // initialize count array to all zero

    for (int i = 1; i <= size; i++)
        count[array[i]]++; // increase number count in count array.

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

    for (int i = size; i >= 1; i--)
    {
        output[count[array[i]]] = array[i];
        count[array[i]] -= 1; // decrease count for same numbers
    }

    for (int i = 1; i <= size; i++)
    {
        array[i] = output[i]; // store output array to main array
    }
}

int main()
{

    int n;
    cout << "Enter the number of elements number?: "<<endl;;
    cin >> n;
    int arr[n + 1]; 
    cout << "Enter elements:" << endl;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    countSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);

}