// Cuenta comparaciones: no depende de la máquina, y sí permite comparar algoritmos.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdio>
#include <vector>

#include "inputs.h"
#include "int_sorts.h"

namespace {

const unsigned SEED = 2026;

long long count_merge(std::vector<int> items) {
    long long comparisons = 0;
    merge_sort_ints(items, comparisons);
    return comparisons;
}

long long count_first(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort_first_ints(items, comparisons);
    return comparisons;
}

long long count_random(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort_random_ints(items, SEED, comparisons);
    return comparisons;
}

long long count_three(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort_three_ints(items, SEED, comparisons);
    return comparisons;
}

long long count_library(std::vector<int> items) {
    long long comparisons = 0;
    std::sort(items.begin(), items.end(), [&comparisons](int a, int b) {
        comparisons++;
        return a < b;
    });
    return comparisons;
}

long long count_stable(std::vector<int> items) {
    long long comparisons = 0;
    std::stable_sort(items.begin(), items.end(), [&comparisons](int a, int b) {
        comparisons++;
        return a < b;
    });
    return comparisons;
}

void row(const char* name, const std::vector<int>& items) {
    std::printf("%-10s %9lld %9lld %9lld %9lld %9lld %9lld\n", name, count_merge(items),
                count_first(items), count_random(items), count_three(items), count_library(items),
                count_stable(items));
}

}  // namespace

int main() {
    const std::size_t n = 4096;
    std::printf("comparaciones con n = %zu\n", n);
    std::printf("%-10s %9s %9s %9s %9s %9s %9s\n", "entrada", "merge", "q.primero", "q.azar", "q.tres",
                "std::sort", "stable");
    row("al azar", random_input(n, SEED));
    row("ordenada", sorted_input(n));
    row("inversa", reversed_input(n));
    row("10 valores", repeated_input(n, 10, SEED));
    row("iguales", std::vector<int>(n, 7));

    std::printf("\nquicksort con el primero como pivote, entrada ordenada\n");
    std::printf("%6s %10s %12s\n", "n", "comparac.", "n(n-1)/2");
    for (std::size_t size : {1000, 2000, 4000, 8000}) {
        long long formula = static_cast<long long>(size) * (static_cast<long long>(size) - 1) / 2;
        std::printf("%6zu %10lld %12lld\n", size, count_first(sorted_input(size)), formula);
    }

    std::printf("\nquicksort con pivote al azar, entrada al azar: promedio de 20 semillas\n");
    std::printf("%8s %11s %11s %7s\n", "n", "comparac.", "2 n ln n", "razón");
    for (std::size_t size : {1000, 10000, 100000, 1000000}) {
        double total = 0;
        for (unsigned seed = 1; seed <= 20; seed++) {
            std::vector<int> items = random_input(size, seed);
            long long comparisons = 0;
            quick_sort_random_ints(items, seed + 100, comparisons);
            total += static_cast<double>(comparisons);
        }
        double average = total / 20;
        double estimate = 2 * static_cast<double>(size) * std::log(static_cast<double>(size));
        std::printf("%8zu %11.0f %11.0f %7.3f\n", size, average, estimate, average / estimate);
    }
    return 0;
}