// Cuenta comparaciones en el mejor caso, el peor caso y el caso promedio.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <numeric>
#include <random>
#include <vector>

// Devuelve el índice de key, o -1. Suma a comparisons cada comparación con un elemento.
int linear_search(const std::vector<int>& values, int key, long long& comparisons) {
    for (std::size_t i = 0; i < values.size(); i++) {
        comparisons++;
        if (values[i] == key) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

// Ordena values y devuelve cuántas comparaciones entre elementos hizo.
long long insertion_sort(std::vector<int>& values) {
    long long comparisons = 0;
    for (std::size_t i = 1; i < values.size(); i++) {
        int current = values[i];
        std::size_t j = i;
        while (j > 0) {
            comparisons++;
            if (values[j - 1] <= current) {
                break;
            }
            values[j] = values[j - 1];
            j--;
        }
        values[j] = current;
    }
    return comparisons;
}

void search_table(int n) {
    std::vector<int> values(static_cast<std::size_t>(n));
    std::iota(values.begin(), values.end(), 0);

    long long best = 0;
    linear_search(values, 0, best);
    long long worst = 0;
    linear_search(values, -1, worst);
    long long all_positions = 0;
    for (int key = 0; key < n; key++) {
        linear_search(values, key, all_positions);
    }
    double average = static_cast<double>(all_positions) / n;
    std::printf("%8d %8lld %12.1f %8lld\n", n, best, average, worst);
}

void sort_table(int n, std::mt19937& generator) {
    std::vector<int> ascending(static_cast<std::size_t>(n));
    std::iota(ascending.begin(), ascending.end(), 0);

    std::vector<int> descending(ascending.rbegin(), ascending.rend());
    std::vector<int> shuffled = ascending;
    std::shuffle(shuffled.begin(), shuffled.end(), generator);

    long long best = insertion_sort(ascending);
    long long random = insertion_sort(shuffled);
    long long worst = insertion_sort(descending);
    assert(std::is_sorted(ascending.begin(), ascending.end()));
    assert(std::is_sorted(shuffled.begin(), shuffled.end()));
    assert(std::is_sorted(descending.begin(), descending.end()));
    std::printf("%8d %10lld %12lld %10lld\n", n, best, random, worst);
}

int main() {
    std::printf("busqueda lineal: comparaciones\n");
    std::printf("%8s %8s %12s %8s\n", "n", "mejor", "promedio", "peor");
    for (int n : {1000, 2000, 4000}) {
        search_table(n);
    }

    std::printf("\nordenamiento por insercion: comparaciones\n");
    std::printf("%8s %10s %12s %10s\n", "n", "ordenado", "al azar", "invertido");
    std::mt19937 generator(2026);
    for (int n : {1000, 2000, 4000}) {
        sort_table(n, generator);
    }
    return 0;
}