#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>

using namespace std;



void print_vec(vector<int> vec, int arr_size) {
    int max_arr;
    if (arr_size > 30) { //если количество символов больше 30, то сортируются все, но выводятся лишь первые 30 отсортированных
        max_arr = 30;
    }
    else {
        max_arr = arr_size;
    }

    for (int i = 0; i < max_arr; i++)
        cout << vec[i] << ' ';
}

void sort_vec(vector<int>& vec) {

    sort(vec.begin(), vec.end()); //сортировка функцией


}

void qsort(int b, int e, vector<int>& vec)
{

    int l = b, r = e;
    int piv = vec[(l + r) / 2]; // Опорным элементом для примера возьмём средний
    while (l <= r)
    {
        while (vec[l] < piv)
            l++;
        while (vec[r] > piv)
            r--;
        if (l <= r)
            swap(vec[l++], vec[r--]);
    }
    if (b < r)
        qsort(b, r, vec);
    if (e > l)
        qsort(l, e, vec);

}


int main()
{
    char answ;
    do {
        int arr_size;
        char answ_input;
        cout << "Enter array size>>";
        cin >> arr_size;
        int a;

        while (cin.fail() || arr_size <= 1 || cin.peek() != '\n')
        {
            cout << "Error, invalid parameters \n";
            cin.clear();
            cin.ignore(10000, '\n');
            cout << "Enter array size>>";
            cin >> arr_size;
        }



        vector <int> vec1;
        vector <int> vec2;
        vec1.reserve(arr_size);
        vec1.reserve(arr_size);


        cout << "How to fill vector?(1 - from keyboard, 2 - random numbers, 3 - random numbers sorted backwards>>";
        cin >> answ_input;
        while (cin.fail() || cin.peek() != '\n' && answ_input != '1' && answ_input != '2' && answ_input != '3')
        {
            cin.clear();
            cin.ignore(10000, '\n');
            cout << "Error, invalid parameters \n";
            cout << "Random numbers or  in vector or sorted backwards[1/2]";
            cin >> answ_input;
        }

        if (answ_input == '1') {
            for (int i = 0; i < arr_size; i++) { //заполняем вектор
                cout << "Enter " << i + 1 << " element>>";
                cin >> a;
                while (cin.fail() || cin.peek() != '\n')
                {
                    cin.clear();
                    cin.ignore(10000, '\n');
                    cout << "Error, invalid parameter \n";
                    cin >> a;
                }
                vec1.push_back(a);
                vec2.push_back(a);
            }
            auto start1 = chrono::high_resolution_clock::now(); //конец отсчёта времени
            sort_vec(vec1);
            auto end1 = chrono::high_resolution_clock::now(); //точка отсчёт времени начала сортировки функции
            chrono::duration <double> duration1 = end1 - start1; //считаем время работы сортировки функцией
            cout << "Library sorted this vector in " << duration1.count() << endl; // считаем время


            auto start2 = chrono::high_resolution_clock::now(); //точка отсчёт времени начала сортировки функции
            qsort(0, (arr_size - 1), vec2);
            auto end2 = chrono::high_resolution_clock::now(); //конец отсчёта времени
            chrono::duration <double> duration2 = end2 - start2; //считаем время работы сортировки функцией
            cout << "Algorithm sorted this vector in " << duration2.count() << endl; // считаем время

            print_vec(vec1, arr_size);
            cout << endl;
            print_vec(vec2, arr_size);

            if (duration1.count() - duration2.count() > 0)
            {
                cout << "The function was faster by " << (duration1.count() / duration2.count()) * 1000 << " ms \n";
            }
            else
            {
                cout << "The algorithm was faster by " << abs((duration1.count() / duration2.count())) * 1000 << " ms \n";
            }

        }
        else if (answ_input == '2') {
            for (int i = 0; i < arr_size; i++) { //заполняем вектор
                a = rand() % 100;
                vec1.push_back(a);
                vec2.push_back(a);
            }
            auto start1 = chrono::high_resolution_clock::now(); //конец отсчёта времени
            sort_vec(vec1);
            auto end1 = chrono::high_resolution_clock::now(); //точка отсчёт времени начала сортировки функции
            chrono::duration <double> duration1 = end1 - start1; //считаем время работы сортировки функцией
            cout << "Library sorted this vector in " << duration1.count() << endl; // считаем время


            auto start2 = chrono::high_resolution_clock::now(); //точка отсчёт времени начала сортировки функции
            qsort(0, (arr_size - 1), vec2);
            auto end2 = chrono::high_resolution_clock::now(); //конец отсчёта времени
            chrono::duration <double> duration2 = end2 - start2; //считаем время работы сортировки функцией
            cout << "Algorithm sorted this vector in " << duration2.count() << endl; // считаем время

            print_vec(vec1, arr_size);
            cout << endl;
            print_vec(vec2, arr_size);

            if (duration1.count() - duration2.count() > 0)
            {
                cout << "The function was faster by " << (duration1.count() / duration2.count()) * 1000 << " ms \n";
            }
            else
            {
                cout << "The algorithm was faster by " << abs((duration1.count() / duration2.count())) * 1000 << " ms \n";
            }
        }
        else if (answ_input == '3') {
            for (int i = 0; i < arr_size; i++) { //заполняем вектор
                a = rand() % 100;
                vec1.push_back(a);
                vec2.push_back(a);
            }

            auto start1 = chrono::high_resolution_clock::now(); //конец отсчёта времени
            sort_vec(vec1);
            for (int i = 0; i < arr_size - 1; i++) {
                swap(vec1[i], vec1[arr_size - 1 - i]);
            }
            auto end1 = chrono::high_resolution_clock::now(); //точка отсчёт времени начала сортировки функции
            chrono::duration <double> duration1 = end1 - start1; //считаем время работы сортировки функцией
            cout << "Library sorted this vector in " << duration1.count() << endl; // считаем время

            auto start2 = chrono::high_resolution_clock::now(); //точка отсчёт времени начала сортировки функции
            qsort(0, (arr_size - 1), vec2);
            for (int i = 0; i < arr_size - 1; i++) {
                swap(vec2[i], vec2[arr_size - 1 - i]);
            }
            auto end2 = chrono::high_resolution_clock::now(); //конец отсчёта времени
            chrono::duration <double> duration2 = end2 - start2; //считаем время работы сортировки функцией
            cout << "Algorithm sorted this vector in " << duration2.count() << endl; // считаем время

            print_vec(vec1, arr_size);
            cout << endl;
            print_vec(vec2, arr_size);

            if (duration1.count() - duration2.count() > 0)
            {
                cout << "The function was faster by " << (duration1.count() / duration2.count()) * 1000 << " ms \n";
            }
            else
            {
                cout << "The algorithm was faster by " << abs((duration1.count() / duration2.count())) * 1000 << " ms \n";
            }
        }



        vec1.clear(); //удаляем векторы
        vec2.clear();

        cout << "\n Do you want to repeat (y/n)>> ";
        cin >> answ;
        while (cin.fail() || cin.peek() != '\n' && answ != 'n' && answ != 'N' && answ != 'Y' && answ != 'y')
        {
            cin.clear();
            cin.ignore(10000, '\n');
            cout << "Error, invalid parameters \n";
            cout << "\n Do you want to repeat (y/n)>> ";
            cin >> answ;
        }
    } while ((answ == 'y') || (answ == 'Y'));
    return 0;
}