---

vector<int> generateArray(int size, const string& type) { //генерация массива
    vector<int> arr(size);
    if (type == "po_vozrast") {
        for (int i = 0; i < size; i++) arr[i] = i;
    }
    else if (type == "reversed") {
        for (int i = 0; i < size; i++) arr[i] = size - i;
    }
    else {
        for (int i = 0; i < size; i++) arr[i] = i;
        mt19937 rng(42);
        shuffle(arr.begin(), arr.end(), rng);
    }
    return arr;
}

double measureSort(void(*sortFunc)(vector<int>&), vector<int> arr) { // таймер
    comparisons = 0;
    swaps = 0;
    auto start = chrono::high_resolution_clock::now();
    sortFunc(arr);
    auto end = chrono::high_resolution_clock::now();
    return chrono::duration<double, milli>(end - start).count();
}

void runExperiments(const string& sortName, void(*sortFunc)(vector<int>&)) {
    cout << "\n=== " << sortName << " ===\n";
    cout << left << setw(10) << "m"
        << setw(12) << "Параметр"
        << setw(20) << "По возрастанию"
        << setw(20) << "По убыванию"
        << setw(20) << "Случайный"
        << "Среднее\n";
    cout << string(82, '-') << "\n";

    const int RUNS = 10;
    vector<int> sizes = { 1000, 10000, 100000 };
    vector<string> types = { "po_vozrast", "reversed", "random" };

    for (int size : sizes) {
        double cmpAvg[3] = {}, swpAvg[3] = {}, timeAvg[3] = {};

        for (int t = 0; t < 3; t++) {
            double totalCmp = 0, totalSwp = 0, totalTime = 0;
            for (int r = 0; r < RUNS; r++) {
                vector<int> arr = generateArray(size, types[t]);
                double ms = measureSort(sortFunc, arr);
                vector<int> arr2 = arr;
                comparisons = 0; swaps = 0;
                sortFunc(arr2);
                totalCmp += comparisons;
                totalSwp += swaps;
                totalTime += ms;
            }
            cmpAvg[t] = totalCmp / RUNS;
            swpAvg[t] = totalSwp / RUNS;
            timeAvg[t] = totalTime / RUNS;
        }

        auto printRow = [&](const string& param, double v[3]) {
            double avg = (v[0] + v[1] + v[2]) / 3.0;
            cout << left << setw(10) << size
                << setw(12) << param
                << setw(20) << fixed << setprecision(1) << v[0]
                << setw(20) << v[1]
                << setw(20) << v[2]
                << avg << "\n";
            };

        printRow("compare", cmpAvg);
        printRow("swap", swpAvg);
        printRow("time(ms)", timeAvg);
        cout << "\n";
    }
}

int main() {
    setlocale(LC_ALL, "ru");
    runExperiments("1. Сортировка выбором", selectionSort);
    runExperiments("2. Сортировка вставками", insertionSort);
    runExperiments("3. Пузырьковая сортировка", bubbleSort);
    runExperiments("4. Пирамидальная сортировка", Pyramid);
    runExperiments("5. Timsort (вариант)", timSort);
    return 0;
}