---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int FillInc(int n, int arr[]){
    for (int i = 0; i < n; i++) arr[i] = i+1;
    return 0;
}

int FillDec(int n, int arr[]){
    for (int i = 0; i < n; i++) arr[i] = n-i;
    return 0;
}

int FillRand(int n, int arr[]){
    for (int i = 0; i < n; i++) arr[i] = rand() % 1000;
    return 0;
}

int CheckSum(int n, int arr[]){
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}

int RunNumber(int n, int arr[]){
    int series = 1;
    for (int i = 0; i < n-1; i++) if(arr[i+1] < arr[i]) series++;
    return series;
}

void PrintMas(int n, int arr[]){
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

void CopyArray(int n, int src[], int dest[]){
    for (int i = 0; i < n; i++) dest[i] = src[i];
}

// Глобальные счетчики
unsigned long long Mf = 0, Cf = 0;
int max_depth = 0, current_depth = 0;

void reset_counters() {
    Mf = 0;
    Cf = 0;
    max_depth = 0;
    current_depth = 0;
}

// Первая версия QuickSort (рекурсивная, два вызова)
void QuickSortV1(int arr[], int L, int R) {
    if (L >= R) return;
    
    current_depth++;
    if (current_depth > max_depth) max_depth = current_depth;
    
    int x = arr[L];
    int i = L, j = R;
    
    do {
        while (arr[i] < x) { Cf++; i++; }
        while (arr[j] > x) { Cf++; j--; }
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            Mf += 3;
            i++;
            j--;
        }
    } while (i <= j);
    
    QuickSortV1(arr, L, j);
    QuickSortV1(arr, i, R);
    
    current_depth--;
}

// Вторая версия QuickSort (рекурсия только для меньшей части)
void QuickSortV2(int arr[], int L, int R) {
    while (L < R) {
        current_depth++;
        if (current_depth > max_depth) max_depth = current_depth;
        
        int x = arr[L];
        int i = L, j = R;
        
        do {
            while (arr[i] < x) { Cf++; i++; }
            while (arr[j] > x) { Cf++; j--; }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                Mf += 3;
                i++;
                j--;
            }
        } while (i <= j);
        
        if (j - L > R - i) {
            QuickSortV2(arr, i, R);
            R = j;
        } else {
            QuickSortV2(arr, L, j);
            L = i;
        }
        
        current_depth--;
    }
}

int main() {
    srand(time(NULL));
    
    // ЗАДАНИЕ 2. Проверка правильности QuickSortV1
    printf("ЗАДАНИЕ 2. Проверка правильности QuickSort\n");
    printf("============================================\n");
    
    int test_n = 10;
    int test_arr[10];
    FillRand(test_n, test_arr);
    
    printf("Исходный массив: ");
    PrintMas(test_n, test_arr);
    printf("Контрольная сумма: %d\n", CheckSum(test_n, test_arr));
    printf("Число серий: %d\n", RunNumber(test_n, test_arr));
    
    int test_copy[10];
    CopyArray(test_n, test_arr, test_copy);
    reset_counters();
    QuickSortV1(test_copy, 0, test_n-1);
    
    printf("\nПосле сортировки: ");
    PrintMas(test_n, test_copy);
    printf("Контрольная сумма: %d\n", CheckSum(test_n, test_copy));
    printf("Число серий: %d\n", RunNumber(test_n, test_copy));
    printf("C = %llu, M = %llu, Мф+Сф = %llu\n\n", Cf, Mf, Cf+Mf);
    
    // ЗАДАНИЕ 3. Таблица трудоемкости
    printf("ЗАДАНИЕ 3. Трудоемкость метода Хоара QuickSort\n");
    printf("================================================\n");
    printf("  N   |  Убывающий  |  Возрастающий  |  Случайный\n");
    printf("---------------------------------------------------\n");
    
    int n_values[] = {100, 200, 300, 400, 500};
    int num_sizes = 5;
    
    for (int i = 0; i < num_sizes; i++) {
        int n = n_values[i];
        int arr_inc[n], arr_dec[n], arr_rand[n];
        int arr_copy[n];
        
        // Убывающий массив
        FillDec(n, arr_dec);
        CopyArray(n, arr_dec, arr_copy);
        reset_counters();
        QuickSortV1(arr_copy, 0, n-1);
        int dec_sum = Cf + Mf;
        
        // Возрастающий массив
        FillInc(n, arr_inc);
        CopyArray(n, arr_inc, arr_copy);
        reset_counters();
        QuickSortV1(arr_copy, 0, n-1);
        int inc_sum = Cf + Mf;
        
        // Случайный массив
        FillRand(n, arr_rand);
        CopyArray(n, arr_rand, arr_copy);
        reset_counters();
        QuickSortV1(arr_copy, 0, n-1);
        int rand_sum = Cf + Mf;
        
        printf(" %3d   |    %5d    |     %5d     |    %5d\n", 
               n, dec_sum, inc_sum, rand_sum);
    }
    printf("===================================================\n");
    
    printf("\nВЫВОД: Метод Хоара QuickSort ");
    printf("СИЛЬНО ЗАВИСИТ от исходной упорядоченности.\n");
    printf("На упорядоченных массивах (возр. и убыв.) трудоемкость O(n²),\n");
    printf("на случайных массивах O(n log n).\n\n");
    
    // ЗАДАНИЕ 4. Глубина рекурсии
    printf("ЗАДАНИЕ 4. Глубина рекурсии QuickSort\n");
    printf("=============================================================\n");
    printf("  N   |     QuickSortV1        |     QuickSortV2        |\n");
    printf("      |  Убыв.  Возр.  Случ.   |  Убыв.  Возр.  Случ.   |\n");
    printf("-------------------------------------------------------------\n");
    
    for (int i = 0; i < num_sizes; i++) {
        int n = n_values[i];
        int arr_inc[n], arr_dec[n], arr_rand[n];
        int arr_copy[n];
        
        // QuickSortV1
        // Убывающий
        FillDec(n, arr_dec);
        CopyArray(n, arr_dec, arr_copy);
        reset_counters();
        QuickSortV1(arr_copy, 0, n-1);
        int dec_depth1 = max_depth;
        
        // Возрастающий
        FillInc(n, arr_inc);
        CopyArray(n, arr_inc, arr_copy);
        reset_counters();
        QuickSortV1(arr_copy, 0, n-1);
        int inc_depth1 = max_depth;
        
        // Случайный
        FillRand(n, arr_rand);
        CopyArray(n, arr_rand, arr_copy);
        reset_counters();
        QuickSortV1(arr_copy, 0, n-1);
        int rand_depth1 = max_depth;
        
        // QuickSortV2
        // Убывающий
        FillDec(n, arr_dec);
        CopyArray(n, arr_dec, arr_copy);
        reset_counters();
        QuickSortV2(arr_copy, 0, n-1);
        int dec_depth2 = max_depth;
        
        // Возрастающий
        FillInc(n, arr_inc);
        CopyArray(n, arr_inc, arr_copy);
        reset_counters();
        QuickSortV2(arr_copy, 0, n-1);

int inc_depth2 = max_depth;
        
        // Случайный
        FillRand(n, arr_rand);
        CopyArray(n, arr_rand, arr_copy);
        reset_counters();
        QuickSortV2(arr_copy, 0, n-1);
        int rand_depth2 = max_depth;
        
        printf(" %3d   |   %3d    %3d    %3d    |   %3d    %3d    %3d    |\n",
               n, dec_depth1, inc_depth1, rand_depth1, 
               dec_depth2, inc_depth2, rand_depth2);
    }
    printf("=============================================================\n");
    
    printf("\nВЫВОД: Вторая версия значительно уменьшает глубину рекурсии,\n");
    printf("особенно на упорядоченных массивах (с O(n) до O(log n)).\n");
    
    return 0;
}