---

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

// Очистка экрана (Linux/Unix)
void clearScreen() {
    printf("\033[H\033[J");
}

// Пауза с ожиданием нажатия Enter
void pause() {
    printf("\nНажмите Enter для продолжения...");
    // очищаем возможный "мусор" во входном буфере
    int c;
    while ((c = getchar()) != '\n' && c != EOF) {}
    getchar();
}

// Функция вывода массива
void printArray(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Функция шейкерной (пузырьковой двунаправленной) сортировки
void shakerSort(int* arr, int size, int srt, long* count) {
    *count = 0;             // Обнуляем счетчик перестановок
    int left = 0;
    int right = size - 1;

    while (left < right) {
        // Проход слева направо ("всплытие" большего/меньшего элемента вправо)
        for (int i = left; i < right; i++) {
            if (srt) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    (*count)++;
                }
            } else {
                if (arr[i] < arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    (*count)++;
                }
            }
        }
        right--;

        // Проход справа налево ("всплытие" элемента влево)
        for (int i = right; i > left; i--) {
            if (srt) {
                if (arr[i - 1] > arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = temp;
                    (*count)++;
                }
            } else {
                if (arr[i - 1] < arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = temp;
                    (*count)++;
                }
            }
        }
        left++;
    }
}

int main() {
    setlocale(LC_ALL, "ru_RU.UTF-8");
    srand((unsigned int)time(NULL));

    FILE* f;
    int size;
    int* arr;
    char ch;
    long count = 0;

    do {
        clearScreen();
        printf("МЕНЮ:\n");
        printf("1 - Сортировка случайных значений по возрастанию\n");
        printf("2 - Сортировка случайных значений по убыванию\n");
        printf("3 - Сортировка возрастающих значений по убыванию\n");
        printf("4 - Ввод своего массива для сортировки\n");
        printf("0 - выход\n");
        printf("Выбор: ");

        // Читаем один символ выбора пункта меню
        scanf(" %c", &ch);

        switch (ch) {
        case '1': {
            // Случайные числа по возрастанию
            clearScreen();
            printf("Введите размер массива: ");
            scanf("%d", &size);
            arr = (int*)malloc(size * sizeof(int));

            // Генерация и запись случайных чисел
            f = fopen("input.txt", "w");
            printf("Исходный массив:\n");
            for (int i = 0; i < size; i++) {
                arr[i] = rand() - rand();
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            // Сортировка и замер времени
            clock_t start = clock();
            shakerSort(arr, size, 1, &count);
            clock_t stop = clock();

            // Запись результата
            f = fopen("output.txt", "w");
            printf("\nОтсортированный массив:\n");
            for (int i = 0; i < size; i++) {
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            printf("\nВремя: %.6lf сек\n", (double)(stop - start) / CLOCKS_PER_SEC);
            printf("Перестановок: %ld\n", count);

            free(arr);
            pause();
            break;
        }

        case '2': {
            // Случайные числа по убыванию
            clearScreen();
            printf("Введите размер массива: ");
            scanf("%d", &size);
            arr = (int*)malloc(size * sizeof(int));

            f = fopen("input.txt", "w");
            printf("Исходный массив:\n");
            for (int i = 0; i < size; i++) {
                arr[i] = rand() - rand();
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            clock_t start = clock();
            shakerSort(arr, size, 0, &count);
            clock_t stop = clock();

            f = fopen("output.txt", "w");
            printf("\nОтсортированный массив:\n");
            for (int i = 0; i < size; i++) {
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            printf("\nВремя: %.6lf сек\n", (double)(stop - start) / CLOCKS_PER_SEC);
            printf("Перестановок: %ld\n", count);

            free(arr);
            pause();
            break;
        }

        case '3': {
            // Упорядоченный по возрастанию массив, сортируем по убыванию
            clearScreen();
            printf("Введите размер массива: ");
            scanf("%d", &size);
            arr = (int*)malloc(size * sizeof(int));

            // Генерация возрастающего массива
            f = fopen("input.txt", "w");
            printf("Исходный массив:\n");
            arr[0] = rand() % 1000;
            for (int i = 1; i < size; i++) {
                arr[i] = arr[i - 1] + rand() % 100 + 1;
            }
            for (int i = 0; i < size; i++) {
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            // Сортировка по убыванию
            clock_t start = clock();
            shakerSort(arr, size, 0, &count);
            clock_t stop = clock();

            f = fopen("output.txt", "w");
            printf("\nОтсортированный массив:\n");
            for (int i = 0; i < size; i++) {
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            printf("\nВремя: %.6lf сек\n", (double)(stop - start) / CLOCKS_PER_SEC);
            printf("Перестановок: %ld\n", count);

            free(arr);
            pause();
            break;
        }

        case '4': {
            // Ручной ввод массива
            clearScreen();
            printf("Введите размер массива: ");
            scanf("%d", &size);
            arr = (int*)malloc(size * sizeof(int));

            printf("Введите %d элементов:\n", size);
            for (int i = 0; i < size; i++) {
                scanf("%d", &arr[i]);
            }

            // Выбор направления сортировки
            printf("Выберите направление (1 - возр., 2 - убыв.): ");
            char dir;
            scanf(" %c", &dir);
            int srt1 = (dir == '1') ? 1 : 0;

            f = fopen("input.txt", "w");
            printf("\nИсходный массив:\n");
            for (int i = 0; i < size; i++) {
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            clock_t start = clock();
            shakerSort(arr, size, srt1, &count);
            clock_t stop = clock();

            f = fopen("output.txt", "w");
            printf("\nОтсортированный массив:\n");
            for (int i = 0; i < size; i++) {
                fprintf(f, "%d ", arr[i]);
            }
            printArray(arr, size);
            fclose(f);

            printf("\nВремя: %.6lf сек\n", (double)(stop - start) / CLOCKS_PER_SEC);
            printf("Перестановок: %ld\n", count);

            free(arr);
            pause();
            break;
        }

        case '0':
            break;

        default:
            break;
        }
    } while (ch != '0');

    return 0;
}