// Mide selección con entradas al azar: comparaciones exactas y tiempo, con -O2 y sin sanitizers.
// Los tiempos dependen de la máquina. Son la mediana de 7 corridas.
#include <algorithm>
#include <cstdio>
#include <random>
#include <vector>

#include "bench.h"
#include "select.h"

int main() {
    std::printf("%9s | %11s %11s | %9s %9s %9s %9s\n", "n", "cmp.azar/n", "cmp.mdm/n", "sort ms", "nth ms", "azar ms", "mdm ms");
    for (int n = 125000; n <= 8000000; n *= 2) {
        std::mt19937 rng(2026);
        std::vector<int> a(n);
        for (int& x : a) {
            x = static_cast<int>(rng() >> 1);
        }
        std::size_t k = a.size() / 2;
        long long random_count = 0;
        long long linear_count = 0;
        std::mt19937 pivot_rng(7);
        int answer = quickselect_random(a, k, pivot_rng, random_count);
        int same = select_linear(a, k, linear_count);
        assert(answer == same);

        double sort_ms = 1000 * median_seconds(7, [&] {
            std::vector<int> copy = a;
            std::sort(copy.begin(), copy.end());
            keep(copy[k]);
        });
        double nth_ms = 1000 * median_seconds(7, [&] {
            std::vector<int> copy = a;
            std::nth_element(copy.begin(), copy.begin() + static_cast<long>(k), copy.end());
            keep(copy[k]);
        });
        double random_ms = 1000 * median_seconds(7, [&] {
            long long ignored = 0;
            keep(quickselect_random(a, k, pivot_rng, ignored));
        });
        double linear_ms = 1000 * median_seconds(7, [&] {
            long long ignored = 0;
            keep(select_linear(a, k, ignored));
        });
        std::printf("%9d | %11.2f %11.2f | %9.1f %9.1f %9.1f %9.1f\n", n,
                    static_cast<double>(random_count) / n, static_cast<double>(linear_count) / n,
                    sort_ms, nth_ms, random_ms, linear_ms);
    }
}