#include <fstream>
#include <iostream>
#include <chrono>

using namespace std;

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

   cout << '\n';
}

void countSort(int *array, int size) {

    int output[size];   // Буффер
    int max = array[0]; // Максимальное значение

    // Находим макс. значение
    for (int i = 1; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }

    // Массив-счётчик
    int count[max + 1];

    // Записываем нули в массив-счётчик
    for (int i = 0; i <= max; ++i)  {
        count[i] = 0;
    }

    // Записываем значения в счётчик
    for (int i = 0; i < size; i++) {
        count[array[i]]++; // увеличичение count
    }

    // Суммирование в массиве-счётчике
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // Увеличение coy
    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--; // уменьшение count
    }

    // Записываем из буфера в результивный массив
    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

int main(int argc, char **argv) {
    srand(time(NULL));
    setlocale(LC_ALL, "rus");

    unsigned int size;
    unsigned int ans;
    fstream Ifile;

    // Меню
    cout << "Выберите размер сортируемого массива:\n"
            "1. 16\n2. 100\n3. 500\n4. 1000\n5. 5000\n";
    cin >> ans;

    switch (ans) {
        case 1:
            size = 16;
            Ifile.open("d16.txt");
            break;
        case 2:
            size = 100 + 2;
            Ifile.open("d100.txt");
            break;
        case 3:
            size = 500 + 2;
            Ifile.open("d500.txt");
            break;
        case 4:
            size = 1000 + 2;
            Ifile.open("d1000.txt");
            break;
        case 5:
            size = 5000 + 2;
            Ifile.open("d5000.txt");
            break;

        default:
            cout << "Ошибка выбора размера массива\n";
            return 1;
    }

    // Считывание из файла в массив
	int* arr = new int[size];
    for (int i = 0; i < size; i++) {
        Ifile >> arr[i];
    }

    // Вывод массива ДО сортировки
	printf("Массив до сортировки: ");
	display(arr, size);

    // Засекаем время до сортировки
    std::chrono::steady_clock::time_point started = std::chrono::high_resolution_clock::now();

    // Сортировка
	countSort(arr, size);

    // Запоминаем время сортировки
    std::chrono::steady_clock::time_point done = std::chrono::high_resolution_clock::now();

    // Вывод массива ПОСЛЕ сортировки
	printf("Массив после сортировки: ");
	display(arr, size);

    // Вывод время сортировки
    cout << "Время сортировки: " << std::chrono::duration_cast<std::chrono::microseconds>(done-started).count() << " мксек." << endl;

    // Запись в новый файл
    ofstream Ofile;

    switch (ans) {
        case 1:
            Ofile.open("d16-s.txt", ios::trunc);
            break;
        case 2:
            Ofile.open("d100-s.txt", ios::trunc);
            break;
        case 3:
            Ofile.open("d500-s.txt", ios::trunc);
            break;
        case 4:
            Ofile.open("d1000-s.txt", ios::trunc);
            break;
        case 5:
            Ofile.open("d5000-s.txt", ios::trunc);
            break;
    }

    Ofile << arr[0];

    for (int i = 1; i < size; i++) {
        Ofile << endl << arr[i];
    }


    Ofile.close();
    delete[] arr;

	return 0;
}