3

#include <cstdlib>
#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

// Алгоритм шейкерной сортировки
void CocktailSort(int arr[], int n) // Шейкерная сортировка, которая принимает в качестве параметров массива и его размер
{
    bool swapped = true; // Инициализация булевой переменной swapped значением true
    int start = 0; // Инициализация целочисленной переменной start нулём
    int end = n - 1; // Инициализация целочисленной переменной end значением n - 1

    while (swapped) { // Пока swapped = true
        // Сброс swapped, так как предыдущая итерация может быть истинной
        swapped = false; // Присвоение переменной swapped значения false

        // Цикл слево направо такой же, как пузырьковая сортирвка
        for (int i = start; i < end; ++i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        // Если ничего не было перемещено, то массив отсортирован
        if (!swapped)
            break;

        // В противном случае сбросить swapped
        swapped = false;

        // Переместить конечную точку на единицу назад потому, что элемент в конце находится на правильном месте
        --end;

        // Цикл справа налево такой же
        for (int i = end - 1; i >= start; --i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        ++start; // Инкрементирование переменной start
    }
}

// Быстрая сортировка
void QuickSort(int* arr, int first, int last) // Быстрая сортировка, которая принимает в качестве параметров указатель на массив,
// первого и последнего элемента
{
    int mid, count; // Объявление переменных mid, count
    int f = first, l = last; // Инициализация переменных f и l
    mid = arr[(f + l) / 2]; //вычисление опорного элемента
    do // Начало цикла
    {
        while (arr[f] < mid) f++; // Пока первый элемент меньше опорного инкрементирование f
        while (arr[l] > mid) l--; // Пока последний элемент больше опорного декрементирование l
        if (f <= l) //перестановка элементов
        {
            count = arr[f]; // Присвоение переменной count значения первого элемента
            arr[f] = arr[l]; // Присвоение первому элементу массива значения последнего  элемента
            arr[l] = count; // Присвоение последнему элементу массива значения переменной count
            f++; // Инкрементирование f
            l--; // Декрементирование l
        }
    } while (f < l); // Пока первый элемент меньше последнего
    if (first < l) QuickSort(arr, first, l); // Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L<last.
    // Для правой части условие аналогично: first < R.
    if (f < last) QuickSort(arr, f, last);
}



void Randomazer(int x[], int n) // Рандомайзер, который принимает в качестве параметров массив и его размер
{
    for (int i = 0; i < n; i++) // Цикл по переменно i в диапазоне от 0 до n не включительно
    {
        x[i] = rand() % 10; // Заполненние массива случайными числами до 10
    }
}

void Print(int x[], int n) // Функция, выводящая массив на экран, которая принимает в качестве параметров массив и его размер
{
    for (int i = 0; i < n; ++i) // Цикл по переменно i в диапазоне от 0 до n не включительно
    {
        cout << x[i] << " "; // Вывод i-го элемента и пробела
    }
    cout << endl; // Перевод строки
}

int main() // Основной алгоритм
{
    setlocale(0, ""); // Установка русского языка в консоле
    int n; // Объявление переменной n

    cout << "Размер массива: 10 или 100?" << endl; // Вывод сообщения "Размер массива: 10 или 100?" с переводом строки
    cin >> n; // Ввод значения переменной n с клавиатуры
    int fisrt = 0, last = n - 1; // Инициализация переменных fisrt и last
    auto* x = new int[n]; // Создание целочисленного динамического массива размера n

    //Randomazer(x, n); // Вызов функции Randomazer с параметрами x и n

    for (int i = 0; i < n; i++) // Цикл по переменно i в диапазоне от 0 до n не включительно
    {
        int el; // Объявление переменной el
        cout << "Введите элемент #" << i + 1 << ": "; cin >> el; // Вывод сообщения "Введите элемент #" i + 1 и ввод значения переменной el с клавиатуры
        x[i] = el; // Присвоение i-му элементу массива значения el
    }

    cout << "Ваш массив" << endl; // Вывод сообщения "Ваш массив" с переводом строки
    Print(x, n); // Вызов функции Print с параметрами x и n

    auto start = high_resolution_clock::now();

    //CocktailSort(x, n); // Вызов функции CocktailSort с параметрами x и n
    QuickSort(x, fisrt, last); // Вызов функции QuickSort с параметрами x, fisrt и last

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);
    cout << "Время выполнения: " << duration.count() << " milliseconds" << endl;

    cout << "Отсортированный массив" << endl; // Вывод сообщения "Очищенный массив" с переводом строки
    Print(x, n); // Вызов функции Print с параметрами x и n

    delete[]x; // Удаление массива x

    system("pause"); // Пауза для просмотра результата
    return 0; // Возврат нуля - индикатор корректности завершения программы
}