// Mide heapsort frente a las ordenaciones de la biblioteca. Compilar con -O2 y sin sanitizers.
// Los tiempos dependen de la máquina.
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"
#include "heapsort.h"

namespace {

template <typename Sorter>
double time_sort(const std::vector<int>& input, Sorter sorter) {
    return median_seconds(5, [&] {
        std::vector<int> items = input;
        sorter(items);
        keep(items[items.size() / 2]);
    });
}

}  // namespace

int main() {
    std::cout << "        n   heapsort  std::sort  stable_sort  heap/sort\n";
    for (int n : {100000, 200000, 400000, 800000, 1600000, 3200000}) {
        std::vector<int> input(n);
        std::iota(input.begin(), input.end(), 0);
        std::mt19937 generator(13);
        std::shuffle(input.begin(), input.end(), generator);
        double heap = time_sort(input, [](std::vector<int>& items) { heapsort(items, std::less<int>()); });
        double quick = time_sort(input, [](std::vector<int>& items) { std::sort(items.begin(), items.end()); });
        double stable =
            time_sort(input, [](std::vector<int>& items) { std::stable_sort(items.begin(), items.end()); });
        std::cout << std::fixed << std::setprecision(4) << std::setw(9) << n << std::setw(11) << heap
                  << std::setw(11) << quick << std::setw(13) << stable << std::setprecision(2)
                  << std::setw(11) << heap / quick << "\n";
    }
    return 0;
}