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

class Array //объявляем класс "Массив"
{
public:
    void fill(int n, int *a) //метод для заполнения массива
    {
        srand(time(NULL));
        for (int i = 0; i < n; i++) //заполняем массив случайными значениями
        {
            a[i] = rand() % 100;
        }
    }
    void print(int n, int *a, bool mode) //метод для вывода значений массива на экран
    {
        if (mode == 0) //вывод неотсортированного массива
        {
            cout << endl << "Unsorted array:" << endl;
            for (int i = 0; i < n; i++)
            {
                cout << a[i] << " ";
            }
            cout << endl; ///
        }
        else //вывод отсортированного массива
        {
            cout << endl << "Sorted array:" << endl;
            for (int i = 0; i < n; i++)
            {
                cout << a[i] << " "; ///
            }
        }
    }
    double bubblesort(int n, int *a) //метод для сортировки "пузырьком"
    {
        clock_t t1 = clock(); //фиксируем время до сортировки
        for (int i = n - 1; i >= 0; i--) //цикл для исключения отсортированных элементов
            for (int j = 0; j < i; j++) //цикл для прогонки элементов
                if (a[j] > a[j + 1]) //если порядок соседних элементов неправильный,
                    swap(a[j], a[j + 1]); //меняем их местами
        clock_t t2 = clock(); //фиксируем время после сортировки
        double sorttime = t2 - t1; //разницу во времени передаем в переменную
        return sorttime; //и возвращаем это значение в функцию
    }
    double shellsort(int n, int *a) //метод для сортировки Шелла
    {
        clock_t t1 = clock(); //фиксируем время до сортировки
        int step = n / 2; //инициализируем шаг
        while (step > 0)//пока шаг не 0
        {
            for (int i = 0; i < (n - step); i++) //будем идти начиная с i-го элемента
            {
                int j = i;
                while (j >= 0 && a[j] > a[j + step]) //пока не пришли к началу массива, и пока рассматриваемый элемент больше чем элемент находящийся на расстоянии шага
                {
                    swap(a[j], a[j + step]); //меняем их местами
                    j--;
                }
            }
            step = step / 2; //уменьшаем шаг
        }
        clock_t t2 = clock(); //фиксируем время после сортировки
        double sorttime = t2 - t1; //разницу во времени передаем в переменную
        return sorttime; //и возвращаем это значение в функцию
    };
    double quicksort(int *a, int left, int right) //метод для быстрой сортировки
    {
        clock_t t1 = clock(); //фиксируем время до сортировки
        int i = left, j = right; int center = a[left + (right - left) / 2]; //объявляем локальные переменные, необходимые для сортировки
        while (i <= j) //пока левый маркер не зашел за правый
        {
            while (a[i] < center) i++; //пока значение элемента под левым маркером меньше значения середины, сдвигаем маркер вправо
            while (a[j] > center) j--; //и пока значение элемента под правым маркером больше значения середины, сдвигаем маркер влево

            if (i <= j) //если левый маркер меньше либо равен правому
            {
                swap(a[i], a[j]); //меняем значение элементов под маркерами местами
                i++; j--; //и смещаем маркеры к центру на 1
            }
        }
        if (i < right) quicksort(a, i, right); //если левый маркер левее конца массива, рекурсивно сортируем отрезок между ними
        if (left < j) quicksort(a, left, j); //если начало массива левее правого маркера, рекурсивно сортируем отрезок между ними
        clock_t t2 = clock(); //фиксируем время после сортировки
        double sorttime = t2 - t1; //разницу во времени передаем в переменную
        return sorttime; //и возвращаем это значение в функцию
    }
};
void main()
{
    Array A;
    int n; cout << "Array size: "; cin >> n; //считываем размер массива
    int type;
    int *a = new int[n]; //объявляем массив заданного размера
    A.fill(n, a); //вызываем функцию для заполнения массива случайными числами
    A.print(n, a, 0); //вызываем функцию для вывода неотсортированного массива на экран
    cout << endl << "Choose sorting type (options:" << endl << "1 - bubble sort, 2 - Shell sort, 3 - quicksort): "; cin >> type;

    switch (type) //выбираем вид сортировки
    {
    case 1: //сортировка "пузырьком"
    {
        A.bubblesort(n, a); //вызываем метод для сортировки
        A.print(n, a, 1); //вызываем метод для вывода массива на экран
        cout << "\n\nBubble Sorting time in milliseconds: " << A.bubblesort(n, a);// / CLOCKS_PER_SEC; //выводим время сортировки в секундах
        break;
    }
    case 2: //сортировка Шелла
    {
        A.shellsort(n, a); //вызываем метод для сортировки
        A.print(n, a, 1); //вызываем метод для вывода массива на экран
        cout << "\n\nShellSorting time in milliseconds: " << A.shellsort(n, a);// / CLOCKS_PER_SEC; //выводим время сортировки в секундах
        break;
    }
    case 3: //быстрая сортировка
    {
        A.quicksort(a, 0, n-1); //вызываем метод для сортировки
        A.print(n, a, 1); //вызываем метод для вывода массива на экран
        cout << "\n\nQuick Sorting time in milliseconds: " << A.quicksort(a, 0, n-1);// / CLOCKS_PER_SEC; //выводим время сортировки в секундах
        break;
    }
    default:
        cout << "\nError: wrong type has been chosen.";
        break;
    }
    delete[]a; //очистка памяти
    _getch(); //задержка экрана
}