// Counting sort frente a std::sort con enteros pequeños. Tiempos con -O2 y un solo hilo.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "counting_sort.h"

template <typename Work>
double best_ms(Work work) {
    double best = -1;
    for (int attempt = 0; attempt < 5; attempt++) {
        const auto begin = std::chrono::steady_clock::now();
        work();
        const std::chrono::duration<double, std::milli> ms = std::chrono::steady_clock::now() - begin;
        if (best < 0 || ms.count() < best) best = ms.count();
    }
    return best;
}

int main() {
    std::cout << "        n          k  counting ms  std::sort ms\n";
    std::cout << std::fixed << std::setprecision(1);
    const std::vector<std::pair<int, int>> sizes = {
        {1000000, 1000}, {4000000, 1000}, {16000000, 1000},
        {1000000, 1000000}, {1000000, 10000000}, {1000, 10000000}};
    for (const auto& [n, k] : sizes) {
        std::mt19937 rng(4);
        std::vector<int> original(static_cast<std::size_t>(n));
        for (int& value : original) value = static_cast<int>(rng() % static_cast<unsigned>(k));
        const double counting = best_ms([&] {
            std::vector<int> a = original;
            counting_sort(a, k);
        });
        const double library = best_ms([&] {
            std::vector<int> a = original;
            std::sort(a.begin(), a.end());
        });
        std::cout << std::setw(9) << n << std::setw(11) << k << std::setw(13) << counting
                  << std::setw(14) << library << '\n';
    }
}