/*
    Algorithms and Data Structures
    Spring 2019
    Assignment #6
    @file RadixSort.cpp
    @author Taiyr Begeyev
    @version 1.0 25/03/19
*/

/*
__________           .__
\__    ___/ _____    |__|  ___.__. _______
  |    |    \__  \   |  | <   |  | \_  __ \
  |    |     / __ \_ |  |  \___  |  |  | \/
  |____|    (____  / |__|  / ____|  |__|
                \/        \/
*/
#include <iostream>
#include <algorithm>
using namespace std;

void CountingSort(int*, int, int);
void RadixSort(int*, int);
void printArr(int*, int);

int howManyDigits(int n) {
    int counter = 0;
    int hey;
    while(n > 0) {
        hey = n % 10;
        n /= 10;
        counter++;
    }
    return counter;
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int *sequence = new int[n + 1];
    cout << "Enter the elements: ";

    for (int i = 0; i < n; i++)
        cin >> sequence[i];

    RadixSort(sequence, n);
    cout << "Sorted Array: " << endl;
    printArr(sequence, n);

    delete[] sequence;

    return 0;
}

/**
 * @brief Counting Sort Algorithm Implementation
 *
 * Algorithm assumes that each of the input elements
 * is an integer in the range 0 to k, for some k. It
 * determines the number of elements less than x, for
 * each input element x. It uses the information to place
 * element x directly into its position in the output array
 *
 * @param A - array to be sorted
 * @param n - number of elements in the array
*/

void CountingSort(int *A, int n, int exp) {
    if (exp == 0)
        exp = 1;
    // create Auxiliary Array
    int max = *max_element(A, A + n);
    //int min = *min_element(A, A + n);
    //int range = max - min + 1;
    int *C = new int[max];
    // create the resultant array
    int *B = new int[n];

    // initialize the array with zeros
    for (int i = 0; i < max; i++) {
        C[i] = 0;
    }
    // iterate through array, calculate and the number
    // of occurences of A[i] to C[A[i]]
    for (int i = 0; i < n; i++) {
        C[( A[i] / exp )]++;
    }

    // determine for each i = 0 .. k how many input elements
    // are less than or equal to i
    for (int i = 1; i < max; i++) {
        C[i] += C[i - 1];
    }

    // place each element from C into its correct sorted position
    for (int i = n - 1; i >= 0; i--) {
        B[C[(A[i] / exp)] - 1] = A[i];
        C[(A[i] / exp)]--;
    }
    for (int i = 0; i < n; i++) {
        A[i] = B[i];
    }

    // deallocate
    delete [] B;
    delete [] C;
}

void RadixSort(int *arr, int n) {
    int maxDigit = 0;

    for (int i = 0; i < n; i++) {
        if (howManyDigits(arr[i]) > maxDigit)
            maxDigit = howManyDigits(arr[i]);
    }
    int exp = 1;
    for (int i = 0; i < maxDigit - 1; i++) {
        exp *= 10;
    }
    for (int i = 0; i < n; i++) {
        CountingSort(arr, n, exp);
        exp /= 10;
    }
}

/**
 * @brief print the passed Array
 * @param array - to be printed
 * @param n - number of elements
*/

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