Sortings

#include <iostream>
#include <Windows.h>
#include <fstream>
#include <ctime>
#include <string>

using namespace std;

void create_array(int*, int, string);
void output_array(int*, int);
void Exchange(int, int, int*);
void Hoar_Sort(int, int*);
void Quick_Sort(int, int, int*);
void Binary_Pyramid_Sort(int, int*);
void Build_Pyramid(int, int, int*);
void Sort_Piramid(int, int*);
void Sifting(int, int, int*);
void BubbleSort(int, int*);

int compare1 = 0;
int replace1 = 0;
int compare2 = 0;
int replace2 = 0;
int compare3 = 0;
int replace3 = 0;

int main()
{
    int q;

    do
    {
        SetConsoleOutputCP(1251);
        SetConsoleCP(1251);

        string s1 = "Sortings_tmp_100.txt";
        string s2 = "Sortings_tmp_1000.txt";

        int size_small, size_big;
        cout << "Введите размер малого массива" << endl;
        cin >> size_small;
        cout << "Введите размер большого массива" << endl;
        cin >> size_big;

        int* small_array = new int[size_small];
        int* big_array = new int[size_big];

        int* small_quick_array = new int[size_small];
        int* big_quick_array = new int[size_big];

        int* small_heap_array = new int[size_small];
        int* big_heap_array = new int[size_big];

        int* small_bubble_array = new int[size_small];
        int* big_bubble_array = new int[size_big];

        create_array(small_array, size_small, s1);
        cout << "Малый массив:" << endl;
        output_array(small_array, size_small);

        for (int i = 0; i < size_small; i++)
        {
            small_bubble_array[i] = small_heap_array[i] = small_quick_array[i] = small_array[i];
        }

        cout << "Быстрая сортировка Хоара (малый массив):" << endl;
        Hoar_Sort(size_small, small_quick_array);
        output_array(small_quick_array, size_small);
        cout << "Пирамидальная сортировка (малый массив):" << endl;
        Binary_Pyramid_Sort(size_small, small_heap_array);
        output_array(small_heap_array, size_small);
        cout << "Сортировка пузырьком (малый массив):" << endl;
        BubbleSort(size_small, small_bubble_array);
        output_array(small_bubble_array, size_small);

        cout << "В быстрой сортировке сравнений: " << compare1 << ", перестановок: " << replace1 << endl;
        cout << "В пирамидальной сортировке сравнений: " << compare2 << ", перестановок: " << replace2 << endl;
        cout << "В сортировке пузырьком сравнений: " << compare3 << ", перестановок: " << replace3 << endl;

        if (compare1 < compare2)
            if (compare1 < compare3)
                cout << "В быстрой сортировке меньше всего сравнений" << endl;
            else cout << "В сортировке пузырьком меньше всего сравнений" << endl;
        else if (compare2 < compare3)
            cout << "В пирамидальной сортировке меньше всего сравнений" << endl;
            else cout << "В сортировке пузырьком меньше всего сравнений" << endl;

         if (replace1 < replace2)
            if (replace1 < replace3)
                cout << "В быстрой сортировке меньше всего перестановок" << endl;
            else cout << "В сортировке пузырьком меньше всего перестановок" << endl;
        else if (replace2 < replace3)
            cout << "В пирамидальной сортировке меньше всего перестановок" << endl;
            else cout << "В сортировке пузырьком меньше всего перестановок" << endl;

        compare1 = compare2 = compare3 = replace1 = replace2 = replace3 = 0;

        /////////////////////////////////////////////////////////////////////

        create_array(big_array, size_big, s2);
        cout << "Большой массив:" << endl;
        output_array(big_array, size_big);

        for (int i = 0; i < size_big; i++)
        {
            big_bubble_array[i] = big_heap_array[i] = big_quick_array[i] = big_array[i];
        }

        cout << "Быстрая сортировка Хоара (большой массив):" << endl;
        Hoar_Sort(size_big, big_quick_array);
        output_array(big_quick_array, size_big);
        cout << "Пирамидальная сортировка (большой массив):" << endl;
        Binary_Pyramid_Sort(size_big, big_heap_array);
        output_array(big_heap_array, size_big);
        cout << "Сортировка пузырьком (большой массив):" << endl;
        BubbleSort(size_big, big_bubble_array);
        output_array(big_bubble_array, size_big);

        cout << "В быстрой сортировке сравнений: " << compare1 << ", перестановок: " << replace1 << endl;
        cout << "В пирамидальной сортировке сравнений: " << compare2 << ", перестановок: " << replace2 << endl;
        cout << "В сортировке пузырьком сравнений: " << compare3 << ", перестановок: " << replace3 << endl;

        if (compare1 < compare2)
            if (compare1 < compare3)
                cout << "В быстрой сортировке меньше всего сравнений" << endl;
            else cout << "В сортировке пузырьком меньше всего сравнений" << endl;
        else if (compare2 < compare3)
            cout << "В пирамидальной сортировке меньше всего сравнений" << endl;
        else cout << "В сортировке пузырьком меньше всего сравнений" << endl;

        if (replace1 < replace2)
            if (replace1 < replace3)
                cout << "В быстрой сортировке меньше всего перестановок" << endl;
            else cout << "В сортировке пузырьком меньше всего перестановок" << endl;
        else if (replace2 < replace3)
            cout << "В пирамидальной сортировке меньше всего перестановок" << endl;
        else cout << "В сортировке пузырьком меньше всего перестановок" << endl;

        cout << "0. Выход" << endl;
        cin >> q;

    } while (q != 0);
}

void create_array(int* array, int size, string s1)
{
    fstream file_1;
    file_1.open(s1, ios::out);

    srand(static_cast<int>(time(0)));

    for (int i = 0; i < size; i++)
    {
        file_1 << rand() % 100;
        file_1 << ' ';
    }
    file_1.close();

    file_1.open(s1, ios::in);
    for (int i = 0; i < size; i++)
        file_1 >> array[i];


    file_1.close();
}

void output_array(int* array, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << array[i] << '\t';
        if (!((i + 1) % 20))
            cout << endl;
    }
    cout << endl;
}

void Exchange(int i, int j, int* array)
{
    int tmp;
    tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

void Hoar_Sort(int size, int* array)
{
    Quick_Sort(0, size - 1, array);
}

void Quick_Sort(int left, int right, int* array)
{
    int i, j, m;
    i = left;
    j = right;

    m = array[(i + j + 1) / 2];
    do
    {
        while (array[i] < m && compare1++)
            i++;
        while (array[j] > m && compare1++)
            j--;
        if (i <= j)
        {
            Exchange(i, j, array);
            replace1++;
            i++;
            j--;
        }

    } while (i <= j);
    if (left < j && compare1++) Quick_Sort(left, j, array);
    if (i < right && compare1++) Quick_Sort(i, right, array);
}

void Binary_Pyramid_Sort(int size, int* array)
{
    //преобразование массива в пирамиду
    Build_Pyramid(size / 2 + 1, size - 1, array);
    //сортировка пирамиды
    Sort_Piramid(size - 1, array);
}

void Build_Pyramid(int size, int r, int* array)
{
    //просеивание элементов пирамиды
    Sifting(size, r, array);
    if (size > 0)
        //рекурсивно вызываем функцию построения
        Build_Pyramid(size - 1, r, array);
}

void Sort_Piramid(int size, int* array)
{
    //переставляем первый элемент пирамиды с последним
    Exchange(0, size, array);
    replace2++;
    //исключаем последний элемент пирамиды
    Sifting(0, size - 1, array);
    //добиваемся того, чтобы массив снова стал пирамидой
    if (size > 1)
        Sort_Piramid(size - 1, array);
}

void Sifting(int left, int right, int* array)
{
    //принцип: каждый потомок должен быть меньше, чем родитель
    int q, p;
    q = 2 * left + 1;  //индекс левого элемента
    p = q + 1;  //индекс правого элемента
    if (q <= right && compare2++)
    {

        if (p <= right && array[p] > array[q] && compare2++)
            q = p;

        if (array[left] < array[q] && compare2++)
        {
            Exchange(left, q, array);
            replace2++;
            Sifting(q, right, array);
        }
    }
}

void BubbleSort(int size, int* array)
{
    int i, j, buf;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
        {
            compare3++;
            if (array[j] > array[j + 1])
            {
                buf = array[j];
                array[j] = array[j + 1];
                array[j + 1] = buf;
                replace3++;
            }
        }
}