---

#include <iostream>                          // подключаем библиотеку ввода-вывода (cin, cout)
#include <cstdlib>                           // подключаем rand(), srand()
#include <ctime>                             // подключаем time() для инициализации генератора случайных чисел
using namespace std;                         // используем стандартное пространство имён, чтобы не писать std::

void log_arr(int* arr, int m) {              // функция вывода массива на экран
    cout << "Sorted Array\n";                // печатаем заголовок
    for (int i = 0; i < m; i++) {            // проходим по всем элементам массива
        cout << arr[i] << ' ';               // выводим текущий элемент и пробел
    }
    cout << endl;                            // переносим строку после вывода массива
}

void bubbleSort(int* arr, int m)             // функция пузырьковой сортировки
{
    bool swapped;                            // флаг: была ли перестановка на текущем проходе
    for (int i = 0; i < m - 1; i++) {        // внешний цикл — количество проходов по массиву
        swapped = false;                     // в начале прохода считаем, что перестановок не было
        for (int j = 0; j < m - i - 1; j++) { // внутренний цикл — сравнение соседних элементов
            if (arr[j] > arr[j + 1]) {       // если текущий элемент больше следующего
                swap(arr[j], arr[j + 1]);    // меняем их местами
                swapped = true;              // отмечаем, что перестановка была
            }
        }
        if (!swapped) break;                 // если перестановок не было — массив уже отсортирован, выходим
    }
}

void shakerSort(int* arr, int m)             // функция шейкерной сортировки
{
    int left = 0;                            // левая граница ещё не отсортированной части
    int right = m - 1;                       // правая граница ещё не отсортированной части
    while (left < right)                     // пока границы не сомкнулись
    {
        for (int i = left; i < right; i++) { // проход слева направо
            if (arr[i] > arr[i + 1]) {       // если элемент больше соседнего справа
                swap(arr[i], arr[i + 1]);    // меняем местами (наибольший "всплывает" вправо)
            }
        }
        right--;                             // сужаем правую границу (там уже стоит максимум)
        for (int i = right; i > left; i--) { // проход справа налево
            if (arr[i - 1] > arr[i]) {       // если левый сосед больше текущего элемента
                swap(arr[i], arr[i - 1]);    // меняем местами (наименьший "тонет" влево)
            }
        }
        left++;                              // сужаем левую границу (там уже стоит минимум)
    }
}

void quickSort(int* arr, int left, int right) // функция быстрой сортировки (границы диапазона)
{
    int i = left;                            // указатель, идущий слева
    int j = right;                           // указатель, идущий справа
    int pivot = arr[(left + right) / 2];     // выбираем опорный элемент (средний по индексу)
    while (i <= j) {                         // пока указатели не пересеклись
        while (arr[i] < pivot) i++;          // двигаем левый указатель, пока элемент меньше pivot
        while (arr[j] > pivot) j--;          // двигаем правый указатель, пока элемент больше pivot
        if (i <= j) {                        // если указатели ещё не пересеклись
            swap(arr[i], arr[j]);            // меняем местами элементы не на своих местах
            i++;                             // сдвигаем левый указатель дальше
            j--;                             // сдвигаем правый указатель дальше
        }
    }
    if (left < j) {                          // если слева от j есть больше одного элемента
        quickSort(arr, left, j);             // рекурсивно сортируем левую часть
    }
    if (i < right) {                         // если справа от i есть больше одного элемента
        quickSort(arr, i, right);            // рекурсивно сортируем правую часть
    }
}

int main()
{
    srand(static_cast<unsigned>(time(0)));   // инициализируем генератор случайных чисел текущим временем
    int choice;                              // переменная для выбора пункта меню
    int m;                                   // переменная для размера массива
    cout << "Select size - ";                // просим пользователя ввести размер массива
    cin >> m;                                // считываем размер массива
    if (m <= 0) return 0;                    // если размер некорректный — завершаем программу

    int* arr = new int[m];                   // выделяем память под массив из m элементов
    for (int i = 0; i < m; i++) {            // заполняем массив случайными числами
        arr[i] = rand() % 133 - 78;          // случайное число в диапазоне от -78 до 54
        cout << arr[i] << ' ';               // выводим сгенерированный элемент
    }
    cout << endl;                            // переносим строку после вывода массива

    while (true)                             // главный цикл программы (меню)
    {
        cout << "\n1. BubbleSort \n2.ShakerSort \n3.QuickSort \n0.Exit\n"; // выводим меню
        cin >> choice;                       // считываем выбор пользователя
        switch (choice)                      // обрабатываем выбор
        {
            case 1: { bubbleSort(arr, m); log_arr(arr, m); break; }        // сортировка пузырьком + вывод
            case 2: { shakerSort(arr, m); log_arr(arr, m); break; }        // шейкерная сортировка + вывод
            case 3: { quickSort(arr, 0, m - 1); log_arr(arr, m); break; }  // быстрая сортировка + вывод
            case 0: { delete[] arr; exit(0); }                            // освобождаем память и выходим
            default: { cout << "Invalid command\n"; }                     // некорректный ввод
        }
    }
}