#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;

int S = 0, C = 0;
void quickSort(int* mass, int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = mass[(left + right) / 2];
    while (i <= j) {
        S++;

        while (mass[i] < pivot)
            i++;
        while (mass[j] > pivot)
            j--;
        if (i <= j) {
            C++;
            tmp = mass[i];
            mass[i] = mass[j];
            mass[j] = tmp;
            i++;
            j--;
        }
    };
    if (left < j)
        quickSort(mass, left, j);
    if (i < right)
        quickSort(mass, i, right);
}
void SelectSort(int mass[], int num) {
    for (int i = 0; i < num; i++)
    {
        int temp = mass[0];

        for (int j = i + 1; j < num; j++)
        {
            C++;
            if (mass[i] > mass[j])
            {
                S++;
                temp = mass[i];
                mass[i] = mass[j];
                mass[j] = temp;
            }
        }
    }
}
void bubbleSort(int* mass, int num)
{
    int tmp;

    for (int i = 0; i < num - 1; ++i)
    {
        for (int j = 0; j < num - 1; ++j)
        {
            C++;
            if (mass[j + 1] < mass[j])
            {
                tmp = mass[j + 1];
                mass[j + 1] = mass[j];
                mass[j] = tmp;
                S++;
            }
        }
    }
}
void GetArray(int* mass, int num) {
    for (int i = 0; i < num; i++) {
        cout << mass[i] << "\t";
    }
}
int main() {
    setlocale(LC_CTYPE, "");
    int num;
    cout << "Кiлькiсть елементiв: ";
    cin >> num;

    int* mass = new int[num];
    for (int i = 0; i < num; i++) {
        mass[i] = rand() % 20 + 100;
        cout << mass[i] << "\t";
    }
    int n;
    cout << "\n\n Виберiть метод сортування:\n 1. Сортування Хоара;\n 2. Сортування вибором;\n 3. Сортування бульбашкою." << endl;
    cin >> n;
    switch (n)
    {
    case 1: {
        cout << endl;
        cout << "Сортування Хоара:" << endl;
        quickSort(mass, 0, num - 1);
    }break;
    case 2: {
        cout << endl;
        cout << "Сортування вибором:" << endl;
        SelectSort(mass, num);
    } break;
    case 3: {
        cout << endl;
        cout << "Сортування бульбашкою:" << endl;
        bubbleSort(mass, num);
    }
    default: break;
    }
    cout << endl;
    cout << "Кiлькiсть порiвнянь: " << C << endl;

    cout << "Кiлькiсть обмiнiв: " << S << endl;
    system("pause");
    return 0;
}