#include <iostream>
using namespace std;

void countSort(int arr[], int n, int exponent) 
{
    int output[n];       //output array
    int count[10] = {0}; //count array to store count of occurrences of digits

    //store count of occurrences of digits
    for (int i = 0; i < n; i++)
        count[(arr[i] / exponent) % 10]++;

    //change count[i] so that count[i] contains the actual position of this digit in output[]
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    //building output array
    for (int i = n - 1; i >= 0; i--) 
    {
        output[count[(arr[i] / exponent) % 10] - 1] = arr[i];
        count[(arr[i] / exponent) % 10]--;
    }

    //copy output array to arr[], so that arr[] now contains sorted numbers according to current digit
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) 
{
    //find maximum number to know number of digits
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    //do counting sort for every digit
    for (int exponent = 1; max / exponent > 0; exponent *= 10)
        countSort(arr, n, exponent);
}

void processRadixSort(int arr[], int n) 
{
    if (n > 1)
        radixSort(arr, n);
}

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

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processRadixSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}