// El adversario contra inserción y contra mergesort: la entrada mala depende del algoritmo.
#include <iomanip>
#include <iostream>
#include <vector>

#include "adversary.h"
#include "comparison_sorts.h"

namespace {

template <typename Sorter>
void play(const char* name, int n, Sorter sorter) {
    Adversary adversary(n);
    std::cout << "  " << std::left << std::setw(11) << name << std::right;
    const auto ask = [&](int i, int j) { return adversary.less(i, j); };
    sorter(n, ask);
    std::cout << std::setw(3) << adversary.count() << " comparaciones, posibles al final: " << adversary.alive()
              << ", entrada:";
    for (int value : adversary.witness()) std::cout << ' ' << value;
    std::cout << '\n';
}

}  // namespace

int main() {
    // Cómo se van acabando las permutaciones, pregunta a pregunta.
    Adversary adversary(4);
    std::cout << "n = 4, inserción. Permutaciones posibles: " << adversary.alive() << '\n';
    insertion_order(4, [&](int i, int j) {
        const bool answer = adversary.less(i, j);
        std::cout << "  ¿e" << i << " < e" << j << "? " << (answer ? "sí" : "no") << ", quedan " << adversary.alive() << '\n';
        return answer;
    });
    std::cout << '\n';

    for (int n : {5, 8}) {
        std::cout << "n = " << n << ", cota " << ceil_log2_factorial(n) << '\n';
        play("inserción", n, [](int size, auto ask) { return insertion_order(size, ask); });
        play("mergesort", n, [](int size, auto ask) { return merge_order(size, ask); });
    }
}

// Un adversario para ordenamientos por comparaciones. No fija la entrada de antemano: guarda todas
// las permutaciones que siguen siendo posibles, y a cada pregunta responde lo que deja más.
#pragma once

#include <algorithm>
#include <cstddef>
#include <numeric>
#include <vector>

class Adversary {
public:
    explicit Adversary(int n) {
        std::vector<int> p(static_cast<std::size_t>(n));
        std::iota(p.begin(), p.end(), 0);
        do {
            alive_.push_back(p);
        } while (std::next_permutation(p.begin(), p.end()));
    }

    // ¿El elemento i es menor que el j? i y j son posiciones de la entrada.
    bool less(int i, int j) {
        count_++;
        std::vector<std::vector<int>> yes;
        std::vector<std::vector<int>> no;
        for (const std::vector<int>& p : alive_) {
            if (p[static_cast<std::size_t>(i)] < p[static_cast<std::size_t>(j)]) {
                yes.push_back(p);
            } else {
                no.push_back(p);
            }
        }
        const bool answer = yes.size() >= no.size();
        alive_ = answer ? std::move(yes) : std::move(no);
        return answer;
    }

    long long count() const { return count_; }
    std::size_t alive() const { return alive_.size(); }
    // Una entrada que es coherente con todas las respuestas dadas hasta ahora.
    const std::vector<int>& witness() const { return alive_.front(); }

private:
    std::vector<std::vector<int>> alive_;
    long long count_ = 0;
};

// Ordena las posiciones 0..n-1 preguntando a Compare, con inserción.
template <typename Compare>
std::vector<int> insertion_order(int n, Compare is_less) {
    std::vector<int> order(static_cast<std::size_t>(n));
    std::iota(order.begin(), order.end(), 0);
    for (std::size_t i = 1; i < order.size(); i++) {
        const int value = order[i];
        std::size_t j = i;
        while (j > 0 && is_less(value, order[j - 1])) {
            order[j] = order[j - 1];
            j--;
        }
        order[j] = value;
    }
    return order;
}

template <typename Compare>
void merge_range(std::vector<int>& order, std::size_t lo, std::size_t hi, Compare& is_less) {
    if (hi - lo < 2) return;
    const std::size_t mid = lo + (hi - lo) / 2;
    merge_range(order, lo, mid, is_less);
    merge_range(order, mid, hi, is_less);
    std::vector<int> merged;
    std::size_t i = lo;
    std::size_t j = mid;
    while (i < mid && j < hi) {
        if (is_less(order[j], order[i])) {
            merged.push_back(order[j++]);
        } else {
            merged.push_back(order[i++]);
        }
    }
    while (i < mid) merged.push_back(order[i++]);
    while (j < hi) merged.push_back(order[j++]);
    std::copy(merged.begin(), merged.end(), order.begin() + static_cast<std::ptrdiff_t>(lo));
}

// Ordena las posiciones 0..n-1 preguntando a Compare, con mergesort.
template <typename Compare>
std::vector<int> merge_order(int n, Compare is_less) {
    std::vector<int> order(static_cast<std::size_t>(n));
    std::iota(order.begin(), order.end(), 0);
    merge_range(order, 0, order.size(), is_less);
    return order;
}

// Ordenamientos que solo miran los datos a través de una comparación, y un comparador
// que cuenta. Así se puede medir exactamente lo que habla la cota inferior.
#pragma once

#include <cstddef>
#include <string>
#include <utility>
#include <vector>

// Compara y anota: cuántas comparaciones van y qué respondió cada una.
// La cadena de respuestas identifica la hoja del árbol de decisiones a la que se llega.
class CountingLess {
public:
    bool operator()(int a, int b) {
        count_++;
        const bool answer = a < b;
        path_ += answer ? 'S' : 'N';
        return answer;
    }

    long long count() const { return count_; }
    const std::string& path() const { return path_; }

private:
    long long count_ = 0;
    std::string path_;
};

// Ordena tres valores con a lo sumo 3 comparaciones.
inline void sort_three(std::vector<int>& a, CountingLess& less) {
    if (less(a[1], a[0])) std::swap(a[0], a[1]);
    // Ahora a[0] < a[1]. Falta ubicar a[2].
    if (less(a[2], a[1])) {
        std::swap(a[1], a[2]);
        if (less(a[1], a[0])) std::swap(a[0], a[1]);
    }
}

inline void insertion_sort(std::vector<int>& a, CountingLess& less) {
    for (std::size_t i = 1; i < a.size(); i++) {
        const int value = a[i];
        std::size_t j = i;
        while (j > 0 && less(value, a[j - 1])) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = value;
    }
}

// Mergesort sobre el rango semiabierto [lo, hi).
inline void merge_sort_range(std::vector<int>& a, std::size_t lo, std::size_t hi, CountingLess& less) {
    if (hi - lo < 2) return;
    const std::size_t mid = lo + (hi - lo) / 2;
    merge_sort_range(a, lo, mid, less);
    merge_sort_range(a, mid, hi, less);
    std::vector<int> merged;
    merged.reserve(hi - lo);
    std::size_t i = lo;
    std::size_t j = mid;
    while (i < mid && j < hi) {
        if (less(a[j], a[i])) {
            merged.push_back(a[j++]);
        } else {
            merged.push_back(a[i++]);
        }
    }
    while (i < mid) merged.push_back(a[i++]);
    while (j < hi) merged.push_back(a[j++]);
    for (std::size_t k = 0; k < merged.size(); k++) a[lo + k] = merged[k];
}

inline void merge_sort(std::vector<int>& a, CountingLess& less) {
    merge_sort_range(a, 0, a.size(), less);
}

// El menor h con 2^h ≥ n!, con enteros. Sirve hasta n = 20, porque 20! cabe en 64 bits.
inline int ceil_log2_factorial(int n) {
    unsigned long long factorial = 1;
    for (int i = 2; i <= n; i++) factorial *= static_cast<unsigned long long>(i);
    int h = 0;
    unsigned long long power = 1;
    while (power < factorial) {
        power *= 2;
        h++;
    }
    return h;
}

// 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';
    }
}

// Counting sort: ordena enteros en [0, k) sin comparar dos elementos entre sí.
#pragma once

#include <cstddef>
#include <vector>

inline void counting_sort(std::vector<int>& a, int k) {
    std::vector<std::size_t> count(static_cast<std::size_t>(k), 0);
    for (int value : a) {
        count[static_cast<std::size_t>(value)]++;  // el valor se usa como índice
    }
    std::size_t next = 0;
    for (int value = 0; value < k; value++) {
        for (std::size_t c = 0; c < count[static_cast<std::size_t>(value)]; c++) {
            a[next++] = value;
        }
    }
}

// Corre las cuatro reglas sobre los contraejemplos de los apuntes.
#include <iostream>
#include <string>
#include <vector>

#include "intervals.h"

namespace {

void print_classes(const std::vector<Interval>& classes) {
    for (const Interval& c : classes) std::cout << " [" << c.start << "," << c.finish << ")";
    std::cout << '\n';
}

void run_rule(const std::string& name, const std::vector<Interval>& result) {
    std::cout << "  " << name << ": " << result.size() << (is_valid(result) ? " (válida)" : " (INVÁLIDA)") << " ->";
    print_classes(result);
}

void report(const std::string& title, const std::vector<Interval>& classes) {
    std::cout << title << "\n  clases:";
    print_classes(classes);
    std::cout << "  óptimo por fuerza bruta: " << max_compatible_brute(classes) << '\n';
    run_rule("empieza antes", rule_earliest_start(classes));
    run_rule("dura menos   ", rule_shortest(classes));
    run_rule("menos cruces ", rule_fewest_conflicts(classes));
    run_rule("termina antes", select_by_finish(classes));
    std::cout << '\n';
}

}  // namespace

int main() {
    report("Contra empieza antes:", {{8, 18}, {9, 11}, {11, 13}, {13, 15}});
    report("Contra dura menos:", {{8, 12}, {12, 16}, {11, 13}});
    const std::vector<Interval> crowded = {
        {0, 2}, {2, 4}, {4, 6}, {6, 8},   // las cuatro de la solución óptima
        {1, 3}, {1, 3}, {1, 3},           // tres iguales entre las dos primeras
        {3, 5},                           // la del centro: solo dos cruces
        {5, 7}, {5, 7}, {5, 7}};          // tres iguales entre las dos últimas
    report("Contra menos cruces:", crowded);

    std::cout << "En esa lista, cruces de cada clase:\n";
    for (std::size_t i = 0; i < crowded.size(); i++) {
        std::cout << "  [" << crowded[i].start << "," << crowded[i].finish << "): " << conflicts(crowded, i)
                  << (in_some_optimum(crowded, i) ? "" : "  (no está en ninguna solución óptima)") << '\n';
    }
    const auto [low, high] = fewest_conflicts_range(crowded);
    std::cout << "Menos cruces, con cualquier forma de romper empates: entre " << low << " y " << high << '\n';
}

// Sigue los ejemplos de los apuntes: selección, aulas y una idea para las aulas que falla.
#include <iostream>
#include <vector>

#include "intervals.h"

int main() {
    const std::vector<Interval> week = {{8, 10}, {9, 11}, {10, 12}, {11, 13}, {8, 13}, {12, 14}, {13, 15}, {15, 16}};
    const auto chosen = select_by_finish(week);
    std::cout << "Selección (" << chosen.size() << " clases, óptimo " << max_compatible_brute(week) << "):";
    for (const Interval& c : chosen) std::cout << " [" << c.start << "," << c.finish << ")";
    std::cout << '\n';

    // El intercambio, a partir de una solución óptima que no se parece a la del greedy.
    std::vector<Interval> optimal = {{9, 11}, {11, 13}, {13, 15}, {15, 16}};
    std::cout << "Intercambio, empezando en:";
    for (const Interval& c : optimal) std::cout << " [" << c.start << "," << c.finish << ")";
    std::cout << '\n';
    for (std::size_t j = 0; j < chosen.size(); j++) {
        if (optimal[j] == chosen[j]) continue;
        optimal[j] = chosen[j];
        std::cout << "  posición " << j + 1 << ":";
        for (const Interval& c : optimal) std::cout << " [" << c.start << "," << c.finish << ")";
        std::cout << (is_valid(optimal) ? "  válida\n" : "  INVÁLIDA\n");
    }

    const auto room = assign_rooms(week);
    std::cout << "Aulas: " << rooms_used(room) << ", máximo simultáneo: " << max_simultaneous(week) << '\n';
    for (std::size_t i = 0; i < week.size(); i++) {
        std::cout << "  [" << week[i].start << "," << week[i].finish << ") -> aula " << room[i] << '\n';
    }

    const std::vector<Interval> tricky = {{10, 11}, {8, 12}, {11, 17}, {15, 16}};
    std::cout << "Clases [10,11) [8,12) [11,17) [15,16)\n";
    std::cout << "  llenar aula por aula con la selección: " << rooms_by_repeated_selection(tricky) << " aulas\n";
    std::cout << "  por orden de inicio: " << rooms_used(assign_rooms(tricky)) << " aulas\n";
    std::cout << "  mínimo por fuerza bruta: " << min_rooms_brute(tricky) << " aulas\n";
    std::cout << "  máximo simultáneo: " << max_simultaneous(tricky) << '\n';

    const std::vector<Interval> touching = {{8, 10}, {10, 12}};
    std::cout << "Clases [8,10) y [10,12): se cruzan = " << (overlap(touching[0], touching[1]) ? "sí" : "no")
              << ", aulas = " << rooms_used(assign_rooms(touching)) << '\n';
}

// Intervalos semiabiertos [start, finish): una clase que termina a las 10 no se cruza con
// una que empieza a las 10. Siempre start < finish.
#pragma once

#include <algorithm>
#include <cstddef>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

struct Interval {
    int start;
    int finish;
    bool operator==(const Interval&) const = default;
};

inline bool overlap(const Interval& a, const Interval& b) {
    return a.start < b.finish && b.start < a.finish;
}

// Válida: ningún par se cruza. No dice nada sobre si es la más grande posible.
inline bool is_valid(const std::vector<Interval>& chosen) {
    for (std::size_t i = 0; i < chosen.size(); i++) {
        for (std::size_t j = i + 1; j < chosen.size(); j++) {
            if (overlap(chosen[i], chosen[j])) return false;
        }
    }
    return true;
}

// La regla correcta: en orden de finalización, tomar lo que no se cruce con lo último tomado.
inline std::vector<Interval> select_by_finish(std::vector<Interval> classes) {
    std::sort(classes.begin(), classes.end(),
              [](const Interval& a, const Interval& b) { return a.finish < b.finish; });
    std::vector<Interval> chosen;
    for (const Interval& c : classes) {
        // Invariante: chosen es válida y está ordenada por tiempo.
        if (chosen.empty() || chosen.back().finish <= c.start) {
            chosen.push_back(c);
        }
    }
    return chosen;
}

// Un greedy genérico: recorre según una clave y toma lo que no se cruce con nada de lo tomado.
template <typename Key>
std::vector<Interval> greedy_by_key(std::vector<Interval> classes, Key key) {
    std::stable_sort(classes.begin(), classes.end(),
                     [&](const Interval& a, const Interval& b) { return key(a) < key(b); });
    std::vector<Interval> chosen;
    for (const Interval& c : classes) {
        const bool fits = std::none_of(chosen.begin(), chosen.end(),
                                       [&](const Interval& x) { return overlap(x, c); });
        if (fits) chosen.push_back(c);
    }
    return chosen;
}

inline std::vector<Interval> rule_earliest_start(const std::vector<Interval>& classes) {
    return greedy_by_key(classes, [](const Interval& c) { return c.start; });
}

inline std::vector<Interval> rule_shortest(const std::vector<Interval>& classes) {
    return greedy_by_key(classes, [](const Interval& c) { return c.finish - c.start; });
}

inline std::vector<Interval> rule_earliest_finish(const std::vector<Interval>& classes) {
    return greedy_by_key(classes, [](const Interval& c) { return c.finish; });
}

// Cuántas clases de `pool` se cruzan con pool[i], sin contarla a ella.
inline int conflicts(const std::vector<Interval>& pool, std::size_t i) {
    int total = 0;
    for (std::size_t j = 0; j < pool.size(); j++) {
        if (j != i && overlap(pool[i], pool[j])) total++;
    }
    return total;
}

// Menos cruces: entre las clases que quedan, tomar la que menos se cruza con las demás que
// quedan, sacar las que se cruzan con ella y repetir. Con empate, la primera de la lista.
inline std::vector<Interval> rule_fewest_conflicts(std::vector<Interval> pool) {
    std::vector<Interval> chosen;
    while (!pool.empty()) {
        std::size_t best = 0;
        for (std::size_t i = 1; i < pool.size(); i++) {
            if (conflicts(pool, i) < conflicts(pool, best)) best = i;
        }
        const Interval picked = pool[best];
        chosen.push_back(picked);
        std::erase_if(pool, [&](const Interval& c) { return overlap(c, picked); });
    }
    return chosen;
}

// Los tamaños que puede dar menos cruces según cómo se resuelvan los empates: (menor, mayor).
inline std::pair<int, int> fewest_conflicts_range(const std::vector<Interval>& pool) {
    if (pool.empty()) return {0, 0};
    int fewest = conflicts(pool, 0);
    for (std::size_t i = 1; i < pool.size(); i++) {
        fewest = std::min(fewest, conflicts(pool, i));
    }
    int low = static_cast<int>(pool.size());
    int high = 0;
    for (std::size_t i = 0; i < pool.size(); i++) {
        if (conflicts(pool, i) != fewest) continue;
        std::vector<Interval> rest;
        for (const Interval& c : pool) {
            if (!overlap(c, pool[i])) rest.push_back(c);
        }
        const auto [rest_low, rest_high] = fewest_conflicts_range(rest);
        low = std::min(low, rest_low + 1);
        high = std::max(high, rest_high + 1);
    }
    return {low, high};
}

// El óptimo por fuerza bruta: prueba los 2^n subconjuntos. Solo para n pequeño.
inline int max_compatible_brute(const std::vector<Interval>& classes) {
    const unsigned n = static_cast<unsigned>(classes.size());
    int best = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        std::vector<Interval> subset;
        for (unsigned i = 0; i < n; i++) {
            if (mask & (1u << i)) subset.push_back(classes[i]);
        }
        if (static_cast<int>(subset.size()) > best && is_valid(subset)) {
            best = static_cast<int>(subset.size());
        }
    }
    return best;
}

// ¿Alguna solución óptima contiene a classes[index]? También por fuerza bruta.
inline bool in_some_optimum(const std::vector<Interval>& classes, std::size_t index) {
    std::vector<Interval> rest;
    for (std::size_t i = 0; i < classes.size(); i++) {
        if (!overlap(classes[i], classes[index])) rest.push_back(classes[i]);
    }
    return 1 + max_compatible_brute(rest) == max_compatible_brute(classes);
}

// Cuántas clases hay a la vez en el momento más lleno. En un mismo instante, primero salen
// las que terminan y luego entran las que empiezan: por eso el fin se ordena con -1.
inline int max_simultaneous(const std::vector<Interval>& classes) {
    std::vector<std::pair<int, int>> events;
    for (const Interval& c : classes) {
        events.push_back({c.start, +1});
        events.push_back({c.finish, -1});
    }
    std::sort(events.begin(), events.end());
    int now = 0;
    int most = 0;
    for (const auto& event : events) {
        now += event.second;
        most = std::max(most, now);
    }
    return most;
}

// Reparte las clases en aulas: devuelve el número de aula (desde 0) de cada clase, en el
// orden de entrada. Por orden de inicio, cada clase va a un aula libre si existe.
inline std::vector<int> assign_rooms(const std::vector<Interval>& classes) {
    std::vector<std::size_t> order(classes.size());
    for (std::size_t i = 0; i < order.size(); i++) order[i] = i;
    std::sort(order.begin(), order.end(), [&](std::size_t x, std::size_t y) {
        if (classes[x].start != classes[y].start) return classes[x].start < classes[y].start;
        return x < y;  // con empate, el orden de entrada: así el resultado no depende de std::sort
    });

    using RoomEnd = std::pair<int, int>;  // (hora en que se desocupa, aula)
    std::priority_queue<RoomEnd, std::vector<RoomEnd>, std::greater<RoomEnd>> busy;
    std::vector<int> room(classes.size());
    int opened = 0;
    for (std::size_t i : order) {
        if (!busy.empty() && busy.top().first <= classes[i].start) {
            room[i] = busy.top().second;
            busy.pop();
        } else {
            room[i] = opened++;
        }
        busy.push({classes[i].finish, room[i]});
    }
    return room;
}

inline int rooms_used(const std::vector<int>& room) {
    return room.empty() ? 0 : 1 + *std::max_element(room.begin(), room.end());
}

// Una idea que suena bien para las aulas: llenar la primera con la selección óptima, quitar
// esas clases, llenar la segunda con lo que quede, y así. Devuelve cuántas aulas usa.
inline int rooms_by_repeated_selection(std::vector<Interval> classes) {
    int rooms = 0;
    while (!classes.empty()) {
        std::vector<Interval> filled = select_by_finish(classes);
        for (const Interval& c : filled) {
            classes.erase(std::find(classes.begin(), classes.end(), c));
        }
        rooms++;
    }
    return rooms;
}

// El mínimo de aulas por vuelta atrás, sin usar ningún teorema: se prueba poner cada clase
// en cada aula abierta o en una nueva. Solo para n pequeño.
inline void min_rooms_search(const std::vector<Interval>& classes, std::size_t next,
                             std::vector<std::vector<Interval>>& rooms, int& best) {
    if (static_cast<int>(rooms.size()) >= best) return;
    if (next == classes.size()) {
        best = static_cast<int>(rooms.size());
        return;
    }
    const Interval c = classes[next];
    for (std::size_t r = 0; r < rooms.size(); r++) {
        const bool fits = std::none_of(rooms[r].begin(), rooms[r].end(),
                                       [&](const Interval& x) { return overlap(x, c); });
        if (fits) {
            rooms[r].push_back(c);
            min_rooms_search(classes, next + 1, rooms, best);
            rooms[r].pop_back();
        }
    }
    rooms.push_back({c});
    min_rooms_search(classes, next + 1, rooms, best);
    rooms.pop_back();
}

inline int min_rooms_brute(const std::vector<Interval>& classes) {
    if (classes.empty()) return 0;
    int best = static_cast<int>(classes.size()) + 1;
    std::vector<std::vector<Interval>> rooms;
    min_rooms_search(classes, 0, rooms, best);
    return best;
}

// Primera tabla: recorre todas las permutaciones y cuenta las comparaciones de dos
// ordenamientos reales, frente a la cota ⌈log₂ n!⌉.
// Segunda tabla: compara log₂ n! con las expresiones de la demostración.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

#include "comparison_sorts.h"

struct Summary {
    long long best = -1;
    long long worst = 0;
    std::size_t leaves = 0;
};

template <typename Sort>
Summary explore(int n, Sort sort_function) {
    std::vector<int> input(static_cast<std::size_t>(n));
    std::iota(input.begin(), input.end(), 0);
    Summary s;
    std::set<std::string> paths;
    do {
        std::vector<int> a = input;
        CountingLess less;
        sort_function(a, less);
        s.best = s.best < 0 ? less.count() : std::min(s.best, less.count());
        s.worst = std::max(s.worst, less.count());
        paths.insert(less.path());
    } while (std::next_permutation(input.begin(), input.end()));
    s.leaves = paths.size();
    return s;
}

int main() {
    std::cout << " n       n!  cota  inserción       mergesort       hojas distintas\n";
    std::cout << "                   mejor  peor     mejor  peor     ins.     merge\n";
    for (int n = 1; n <= 9; n++) {
        const Summary ins = explore(n, insertion_sort);
        const Summary mer = explore(n, merge_sort);
        unsigned long long factorial = 1;
        for (int i = 2; i <= n; i++) factorial *= static_cast<unsigned long long>(i);
        std::cout << std::setw(2) << n << std::setw(9) << factorial << std::setw(6)
                  << ceil_log2_factorial(n) << std::setw(8) << ins.best << std::setw(6) << ins.worst
                  << std::setw(9) << mer.best << std::setw(6) << mer.worst << std::setw(9)
                  << ins.leaves << std::setw(10) << mer.leaves << '\n';
    }

    std::cout << '\n' << "       n     (n/4) log n   (n/2) log(n/2)        log n!         n log n\n";
    std::cout << std::fixed << std::setprecision(0);
    double log_factorial = 0;
    int n = 1;
    for (int target : {4, 16, 256, 4096, 65536, 1048576}) {
        while (n < target) {
            n++;
            log_factorial += std::log2(n);
        }
        const double m = n;
        std::cout << std::setw(8) << n << std::setw(15) << m / 4 * std::log2(m) << std::setw(17)
                  << m / 2 * std::log2(m / 2) << std::setw(14) << log_factorial << std::setw(16)
                  << m * std::log2(m) << '\n';
    }
}

// Mide quicksort: los conteos son exactos y salen iguales con la misma semilla.
// Los tiempos dependen de la máquina. Compilado con -O2.
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "quicksort.h"

using Sorter = void (*)(std::vector<int>&, int, int, Pivot, std::mt19937&, QuickStats&, int);

std::vector<int> make_input(const std::string& kind, int n, std::mt19937& rng) {
    std::vector<int> a(static_cast<std::size_t>(n));
    if (kind == "iguales") return a;
    std::iota(a.begin(), a.end(), 0);
    if (kind == "al azar") {
        for (std::size_t i = a.size(); i > 1; i--) std::swap(a[i - 1], a[rng() % i]);
    }
    return a;
}

void row(const std::string& name, Sorter sorter, Pivot rule, const std::string& kind, int n) {
    std::mt19937 rng(2026);
    std::vector<int> a = make_input(kind, n, rng);
    QuickStats stats;
    const auto begin = std::chrono::steady_clock::now();
    sorter(a, 0, n, rule, rng, stats, 1);
    const std::chrono::duration<double, std::milli> ms = std::chrono::steady_clock::now() - begin;
    if (!std::is_sorted(a.begin(), a.end())) std::cout << "NO QUEDO ORDENADO\n";
    std::cout << std::left << std::setw(18) << name << std::setw(10) << kind << std::right
              << std::setw(7) << n << std::setw(12) << stats.comparisons << std::setw(8)
              << stats.max_depth << std::setw(8) << std::setprecision(2) << std::fixed
              << static_cast<double>(stats.comparisons) / (n * std::log2(n)) << std::setw(10)
              << std::setprecision(1) << ms.count() << '\n';
}

int main() {
    std::cout << "pivote y partición  entrada       n  comparac.  niveles  c/nlogn      ms\n";
    Sorter two = quicksort_two_way;
    Sorter three = quicksort_three_way;
    for (int n : {4000, 16000, 64000}) {
        row("primero, en dos", two, Pivot::First, "ordenada", n);
        row("primero, en dos", two, Pivot::First, "al azar", n);
        row("azar, en dos", two, Pivot::Random, "ordenada", n);
        row("azar, en dos", two, Pivot::Random, "al azar", n);
        row("azar, en dos", two, Pivot::Random, "iguales", n);
        row("azar, en tres", three, Pivot::Random, "iguales", n);
        row("azar, en tres", three, Pivot::Random, "ordenada", n);
        std::cout << '\n';
    }

    // La misma entrada ordenada, con 1000 semillas: lo único que cambia es el azar.
    const int n = 64000;
    long long min_c = -1;
    long long max_c = 0;
    long long sum_c = 0;
    int min_d = n;
    int max_d = 0;
    long long sum_d = 0;
    long long calls = 0;
    long long good = 0;
    const int seeds = 1000;
    for (int seed = 1; seed <= seeds; seed++) {
        std::mt19937 rng(static_cast<unsigned>(seed));
        std::vector<int> a = make_input("ordenada", n, rng);
        QuickStats stats;
        quicksort_two_way(a, 0, n, Pivot::Random, rng, stats, 1);
        min_c = min_c < 0 ? stats.comparisons : std::min(min_c, stats.comparisons);
        max_c = std::max(max_c, stats.comparisons);
        sum_c += stats.comparisons;
        min_d = std::min(min_d, stats.max_depth);
        max_d = std::max(max_d, stats.max_depth);
        sum_d += stats.max_depth;
        calls += stats.large_calls;
        good += stats.good_pivots;
    }
    std::cout << "entrada ordenada, n = " << n << ", " << seeds << " semillas\n";
    std::cout << "comparaciones: mínimo " << min_c << ", promedio " << sum_c / seeds << ", máximo " << max_c << '\n';
    std::cout << "niveles:       mínimo " << min_d << ", promedio " << sum_d / seeds << ", máximo " << max_d << '\n';
    std::cout << "pivotes buenos, en llamadas de 16 o más elementos: " << std::setprecision(1)
              << 100.0 * static_cast<double>(good) / static_cast<double>(calls) << " %\n";
}

// Tamaños de los rangos por nivel, con 16 elementos ya ordenados. Un punto es un rango de un elemento.
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

#include "quicksort.h"

namespace {

using Levels = std::map<int, std::vector<int>>;

void sizes(std::vector<int>& a, int lo, int hi, Pivot rule, std::mt19937& rng, int depth, Levels& levels) {
    if (hi - lo < 1) return;
    levels[depth].push_back(hi - lo);
    if (hi - lo < 2) return;
    choose_pivot(a, lo, hi, rule, rng);
    const int pivot = a[static_cast<std::size_t>(lo)];
    int p = lo;
    for (int i = lo + 1; i < hi; i++) {
        if (a[static_cast<std::size_t>(i)] < pivot) {
            p++;
            std::swap(a[static_cast<std::size_t>(i)], a[static_cast<std::size_t>(p)]);
        }
    }
    std::swap(a[static_cast<std::size_t>(lo)], a[static_cast<std::size_t>(p)]);
    sizes(a, lo, p, rule, rng, depth + 1, levels);
    sizes(a, p + 1, hi, rule, rng, depth + 1, levels);
}

void show(const char* title, Pivot rule) {
    std::vector<int> a(16);
    std::iota(a.begin(), a.end(), 0);
    std::mt19937 rng(7);
    Levels levels;
    sizes(a, 0, 16, rule, rng, 1, levels);
    std::cout << title << '\n';
    for (const auto& [depth, list] : levels) {
        std::cout << "  nivel " << depth << ":";
        for (int size : list) {
            if (size == 1) {
                std::cout << " .";
            } else {
                std::cout << ' ' << size;
            }
        }
        std::cout << '\n';
    }
}

}  // namespace

int main() {
    show("Primer elemento como pivote:", Pivot::First);
    show("Pivote al azar, semilla 7:", Pivot::Random);
}