#include "ReadWriter.h"
//iostream, fstream включены в ReadWriter.h
using namespace std;

union un
{
    unsigned int numb;
    unsigned char int_in_char[4];
};


int findMax(un *numbers, int index, int array_size)
{
    int max = numbers[0].int_in_char[index];
    for (int i = 1; i < array_size; ++i)
    {
        if (numbers[i].int_in_char[index] > max) max = numbers[i].int_in_char[index];
    }
    return max;
}

void initialize_by_zeros(int *tmp, int size)
{
    for (int i = 0; i < size; ++i)
    {
        tmp[i] = 0;
    }
}


// Функция цифровой сортировки
void radixSort(int *numbers, int array_size)
{
    un *_un = new un[array_size];
    for (int l = 0; l < array_size; ++l)
    {
        _un[l].numb = numbers[l];
    }

    for (int i = 0; i < 4; ++i)
    {
        int max = (findMax(_un, i, array_size) + 1);
        int help_array[max];
        initialize_by_zeros(help_array, max);

        for (int j = 0; j < array_size; ++j)
        {
            ++help_array[_un[j].int_in_char[i]];
        }

        for (int j = 1; j < max; ++j)
        {
            help_array[j] += help_array[j - 1];
        }

        for (int k = array_size - 1; k >= 0; --k)
        {
            numbers[--help_array[_un[k].int_in_char[i]]] = _un[k].numb;
        }

        for (int l = 0; l < array_size; ++l)
        {
            _un[l].numb = numbers[l];
        }

    }
   	delete [] _un;

}

//Не удалять и не изменять метод main без крайней необходимости.
//Необходимо добавить комментарии, если все же пришлось изменить метод main.
int main()
{
    //Объект для работы с файлами
    ReadWriter rw;

    int *brr = nullptr;
    int n;

    //Ввод из файла
    n = rw.readInt();

    brr = new int[n];
    rw.readArray(brr, n);

    //Запуск сортировки, ответ в том же массиве (brr)
    radixSort(brr, n);

    //Запись в файл
    rw.writeArray(brr, n);

    //освобождаем память
    delete[] brr;

    return 0;
}