s3

#include <chrono>
#include <iostream>
#include <Windows.h>

// ОПРЕДЕЛЕНИЕ СТРУКТУРЫ ДАННЫХ ДЛЯ СОРТИРОВКИ
struct DATA {
    __int64* mas; // МАССИВ ДАННЫХ
    __int64 size; // РАЗМЕР
    __int64 min;  // МИНИМАЛЬНОЕ ЗНАЧЕНИЕ
    __int64 max;  // МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ
};

// ТИП СОРТИРОВКИ (ДЛЯ ПЕРЕДАЧИ В ФУНКЦИЮ)
enum type
{
    typeShakeSort, typeShellSort
};

typedef struct DATA DATA;

// ФУНКЦИЯ ОТОБРАЖЕНИЯ КУРСОРА В КОНСОЛИ
void ShowConsoleCursor(bool showFlag)
{
    HANDLE out = GetStdHandle(STD_OUTPUT_HANDLE);

    CONSOLE_CURSOR_INFO cursorInfo;

    GetConsoleCursorInfo(out, &cursorInfo);
    cursorInfo.dwSize = 1;
    cursorInfo.bVisible = showFlag;
    SetConsoleCursorInfo(out, &cursorInfo);
}

// ФУНКЦИЯ НАХОЖДЕНИЯ СЛУЧАЙНОГО ЧИСЛА
int random(__int64 N)
{
    int result = rand() % N;
    return result;
}

// ФУНКЦИЯ ФОРМИРОВАНИЯ СЛУЧАЙНОГО МАССИВА ДАННЫХ
int formRandArray(DATA* data)
{
    if (data->min > data->max) return -1;
    for (__int64 i = 0; i < data->size; i++)
    {
        data->mas[i] = data->min + random(data->max - data->min);
    }
    return 0;
}

// ФУНКЦИЯ ПЕРЕСТАНОВКИ ЭЛЕМЕНТОВ ДАННЫХ МЕСТАМИ
template <class T>
void Swap(T& a, T& b)
{
    T tmp = NULL;
    tmp = a;
    a = b;
    b = tmp;
    return;
}

// ФУНКЦИЯ ВЫВОДА МАССИВА НА ЭКРАН
void printMas(DATA& data)
{
    for (int i = 0; i < data.size; i++)
        std::cout << data.mas[i] << ' ';
    std::cout << '\n';
}

std::pair<int, int> ShakeSort(DATA& data) // КОКТЕЙЛЬНАЯ СОРТИРОВКА
{
    std::pair<int, int> countPair; // ВОЗВРАЩАЕМЫЙ АРГУМЕНТ ТИПА "ПАРА"

    int countComp = 0; // ЧИСЛО СРАВНЕНИЙ
    int countSwap = 0; // ЧИСЛО ПЕРЕАДРЕСАЦИЙ
    int i = 0;         // ИНДЕКСНАЯ ПЕРЕМЕННАЯ
    int n = data.size - 1; // РАЗМЕР ДАННЫХ

    bool isSorted = false; // ФЛАГ "МАССИВ ОТСОРТИРОВАН"

    // ПОКА МАССИВ НЕ ОТСОРТИРОВАН
    while (!isSorted)
    {
        // МАССИВ ОТСОРТИРОВАН
        isSorted = true;
        // ЦИКЛ ПО МАССИВУ  ОТ ПЕРВОГО ДО ПОСЛЕДНЕГО ЭЛЕМЕНТА
        for (int j = i; j < n; j++)
        {
            // ЕСЛИ ТЕКУЩИЙ ЭЛЕМЕНТ БОЛЬШЕ СЛЕДУЮЩЕГО
            if (data.mas[j] > data.mas[j + 1])
            {
                // ПЕРЕМЕНА ЭЛЕМЕНТОВ МЕСТАМИ
                Swap(data.mas[j], data.mas[j + 1]);
                // УВЕЛИЧЕНИЕ ЧИСЛА ПЕРЕСТАНОВОК
                countSwap++;
                // МАССИВ НЕ ОТСОРТИРОВАН
                isSorted = false;
            }
            // УВЕЛИЧЕНИЕ ЧИСЛА СРАВНЕНИЙ
            countComp++;
        }
        // ЕСЛИ МАССИВ ОТСОРТИРОВАН
        if (isSorted)
            break; // ВЫХОДИМ ИЗ ФУНКЦИИ
        // УМЕНЬШАЕМ ПРАВУЮ ГРАНИЦУ НА 1
        n--;

        // МАССИВ ОТСОРТИРОВАН
        isSorted = true;
        // ЦИКЛ ОТ ПОСЛЕДНЕГО ЭЛЕМЕНТА ДО ПЕРВОГО
        for (int k = n - 1; k >= i; k--)
        {
            // ЕСЛИ ТЕКУЩИЙ ЭЛЕМЕНТ БОЛЬШЕ ПРЕДЫДУЩЕГО
            if (data.mas[k] > data.mas[k + 1])
            {
                // ПЕРЕМЕНА ЭЛЕМЕНТОВ МАССИВА МЕСТАМИ
                Swap(data.mas[k], data.mas[k + 1]);
                // УВЕЛИЧЕНИЕ ЧИСЛА ПЕРЕСТАНОВОК
                countSwap++;
                // МАССИВ НЕ ОТСОРТИРОВАН
                isSorted = false;
            }
            // УВЕЛИЧЕНИЕ ЧИСЛА СРАВНЕНИЙ
            countComp++;
        }
        // УВЕЛИЧИВАЕМ ЛЕВУЮ ГРАНИЦУ НА 1
        i++;
    }

    countPair.first = countSwap;  // ПЕРВОЕ ЗНАЧЕНИЕ "ПАРЫ" - ЧИСЛО ПЕРЕСТАНОВОК
    countPair.second = countComp; // ВТОРОЕ ЗНАЧЕНИЕ "ПАРЫ" - ЧИСЛО СРАВНЕНИЙ
    return countPair;             // ФУНКЦИЯ ВОЗВРАЩАЕТ НАЙДЕННУЮ "ПАРУ" ЧИСЕЛ
}

std::pair<int, int> ShellSort(DATA& data) // СОРТИРОВКА ШЕЛЛА
{
    std::pair<int, int> countPair;

    int countComp = 0;
    int countSwap = 0;
    int h = 0;

    while (h < data.size / 3)
    {
        h = 3 * h + 1;
    }

    for (h; h > 0; h = (h - 1) / 3)
    {
        for (int i = h; i < data.size; i++)
        {
            int j = i;
            int tmp = data.mas[i];

            for (j = i; j >= h && data.mas[j - h] > tmp; j -= h)
            {
                countComp++;
                countSwap++;
                data.mas[j] = data.mas[j - h];

            }
            countComp++;
            data.mas[j] = tmp;
            countSwap++;
        }
    }

    countPair.first = countSwap;
    countPair.second = countComp;
    return countPair;
}

std::pair<int, int> ShakeSortPrint(DATA& data) // КОКТЕЙЛЬНАЯ СОРТИРОВКА (С ВЫВОДОМ)
{
    std::pair<int, int> countPair;

    int countComp = 0;
    int countSwap = 0;
    int i = 0;
    int n = data.size - 1;

    bool isSorted = false;

    while (!isSorted)
    {
        isSorted = true;
        for (int j = i; j < n; j++)
        {
            if (data.mas[j] > data.mas[j + 1])
            {
                Swap(data.mas[j], data.mas[j + 1]);
                countSwap++;
                printMas(data);
                isSorted = false;
            }
            countComp++;
        }
        if (isSorted)
            break;
        n--;

        isSorted = true;
        for (int k = n - 1; k >= i; k--)
        {
            if (data.mas[k] > data.mas[k + 1])
            {
                Swap(data.mas[k], data.mas[k + 1]);
                countSwap++;
                printMas(data);
                isSorted = false;
            }
            countComp++;
        }
        i++;
    }

    countPair.first = countSwap;
    countPair.second = countComp;
    return countPair;
}

std::pair<int, int> ShellSortPrint(DATA& data) // СОРТИРОВКА ШЕЛЛА (С ВЫВОДОМ)
{
    std::pair<int, int> countPair;

    int countComp = 0;
    int countSwap = 0;
    int h = 0;

    while (h < data.size / 3)
    {
        h = 3 * h + 1;
    }

    std::cout << "h = " << h << ": ";
    printMas(data);

    for (h; h > 0; h = (h - 1) / 3)
    {
        for (int i = h; i < data.size; i++)
        {
            int j = i;
            int tmp = data.mas[i];

            for (j = i; j >= h && data.mas[j - h] > tmp; j -= h)
            {
                countComp++;
                countSwap++;
                data.mas[j] = data.mas[j - h];
                std::cout << "h = " << h << ": ";
                printMas(data);
            }
            countComp++;
            data.mas[j] = tmp;
            countSwap++;
            std::cout << "h = " << h << ": ";
            printMas(data);
        }
        std::cout << "h = " << h << ": ";
        printMas(data);
    }

    countPair.first = countSwap;
    countPair.second = countComp;
    return countPair;
}

// ФУНКЦИЯ ДЛЯ ПОЛУЧЕНИЯ ВРЕМЕНИ, ЗАТРАЧЕННОГО НА ВЫПОЛНЕНИЕ СОРТИРОВКИ УКАЗАННЫМ ТИПОМ
auto getRunTimeMS(DATA& data, type Type, std::pair<int, int>& countPair)
{
    std::chrono::steady_clock::time_point t_start, t_end;
    if (Type == typeShakeSort)
    {
        t_start = std::chrono::high_resolution_clock::now();
        countPair = ShakeSort(data);
        t_end = std::chrono::high_resolution_clock::now();
    }
    if (Type == typeShellSort)
    {
        t_start = std::chrono::high_resolution_clock::now();
        countPair = ShellSort(data);
        t_end = std::chrono::high_resolution_clock::now();
    }

    auto t_elapsed = std::chrono::duration <double>(t_end - t_start);
    return t_elapsed.count() * 1000;
}

int main()
{
    system("color F0");
    ShowConsoleCursor(false);

    int ArrayCount = 0;
    std::pair<int, int> countPair;
    DATA data{ NULL, 9, 1, 100000 };
    data.mas = new __int64[data.size];

    formRandArray(&data);

    std::cout << "ShellSort:\n\n";
    countPair = ShellSortPrint(data);
    std::cout << "\ncountSwap = " << countPair.first << " countComp = " << countPair.second << "\n\n";

    formRandArray(&data);

    std::cout << "\n--------------------------------\nShakeSort:\n\n";
    countPair = ShakeSortPrint(data);
    std::cout << "\ncountSwap = " << countPair.first << " countComp = " << countPair.second << "\n\n";

    delete[] data.mas;

    std::cout << "\n--------------------------------\n\n";

    ArrayCount = 5;
    for (int i = 0; i < 7; i++)
    {
        __int64 ShakeSortComp = 0;
        __int64 ShellSortComp = 0;
        double  ShakeSortTime = 0.0;
        double  ShellSortTime = 0.0;
        __int64 ShakeSortSwap = 0;
        __int64 ShellSortSwap = 0;

        std::cout << "n = " << 5000 + i * 7000 << ". Array count = " << ArrayCount << "\n\n";

        for (int j = 0; j < ArrayCount; j++)
        {
            countPair.first = 0;
            countPair.second = 0;

            data.size = 5000 + i * 7000;
            data.mas = new __int64[data.size];
            formRandArray(&data);

            ShakeSortTime += getRunTimeMS(data, typeShakeSort, countPair);
            ShakeSortSwap += countPair.first;
            ShakeSortComp += countPair.second;

            delete[] data.mas;

            countPair.first = 0;
            countPair.second = 0;


            data.mas = new __int64[data.size];
            formRandArray(&data);

            ShellSortTime += getRunTimeMS(data, typeShellSort, countPair);
            ShellSortSwap += countPair.first;
            ShellSortComp += countPair.second;

            delete[] data.mas;

            ShowConsoleCursor(false);
            std::cout << ((j + 1) * 100) / ArrayCount << "% of arrays processed. \r" << std::flush;
        }

        ShakeSortComp /= ArrayCount;
        ShellSortComp /= ArrayCount;
        ShakeSortSwap /= ArrayCount;
        ShellSortSwap /= ArrayCount;
        ShakeSortTime /= ArrayCount;
        ShellSortTime /= ArrayCount;

        std::cout << "\n\n";
        std::cout << "\tShakeSort:\n" << "\t\tAvgSwaps = " << ShakeSortSwap << "\tAvgComps = " << ShakeSortComp << "\tAvgTime = " << ShakeSortTime << " ms\n";
        std::cout << "\tShellSort:\n" << "\t\tAvgSwaps = " << ShellSortSwap << "\tAvgComps = " << ShellSortComp << "\tAvgTime = " << ShellSortTime << " ms\n";
        std::cout << "\n\n";
    }

    return 0;
}