#include "stdafx.h"
#include<iostream>
#include<windows.h>
#include<ctime>

using namespace std;

void random(int *mac, size_t n);
void vstav(int *mac, size_t n);
void shell(int *macc, size_t n);
void user_cout_mas(int *mas, size_t size);

int main()

{
    setlocale(LC_ALL, "rus");
    srand(time(NULL));

    cout << "Киселева Анна. Группа 3.1. 7 Задача." << endl;
    cout << "Написать программу, в которой запрашивается размер " << endl ;
    cout << "массива (массив заполняется случайными числами), " << endl;
    cout << "выбор из двух заданных сортировок, есть выбор " << endl;
    cout << "показывать или не показывать массив до и после " << endl;
    cout << "сортировки. (Данные сортировки: Вставками и Шелла)" << endl;

    size_t n;
    char x, d;

    cout << endl << "Введите количество элементов массива " << endl;
    cin >> n;
    int *mac = new int[n];
    random(mac, n);

    user_cout_mas(mac, n);

    cout << endl;
    cout << "Введите 0,чтобы выйти." << endl;;
    cout << "Введите 1 для сортировки вставками." << endl;
    cout << "Введите 2 для сортировки Шелла." << endl;;
    cin >> x;

    switch (x)
    {
        case'0':return 0;
        case'1':
            vstav(mac, n);
            break;
        case '2':
            shell(mac, n);
        default:
            cout << "Вы в своей жизни сделали неправильный выбор..." << endl;
            break;
    }
    //system("pause");
    return 0;
}


void random(int *mac, size_t n)
{
    for (int i = 0; i<n; i++)
        mac[i] = rand() % 101 - 50;
}


void vstav(int *mac, size_t n)
{
    long double start, finish, time_work;
    start = clock();
    int x;
    size_t i, j;
    {
        for (i = 0; i <n; i++)
        { // цикл проходов, i - номер прохода
            x = mac[i];
            // поиск места элемента в готовой последовательности
            for (j = i - 1; j >= 0 && mac[j] > x; j--)
                mac[j + 1] = mac[j]; // сдвигаем элемент направо, пока не дошли
                                     // место найдено, вставить элемент
            mac[j + 1] = x;
        }
    }
    finish = clock();

    user_cout_mas(mac, n);

    time_work = 1.0 * (finish - start) / CLOCKS_PER_SEC;
    cout << "Время работы сортировки вставками: " << time_work << "cek" << endl;
}


void shell(int *mac, size_t n)
{
    long double start, finish, time_work;
    start = clock();
    int d = n / 2;
    while (d > 0)
    {
        for (size_t i = 0; i < n - d; i++)
        {
            int j = i;
            while (j >= 0 && mac[j] > mac[j + d])
            {
                swap(mac[j], mac[j + d]);
                j--;
            }
        }
        d /= 2;
    }
    finish = clock();

    user_cout_mas(mac, n);

    time_work = (finish - start) / CLOCKS_PER_SEC;
    cout << "Время работы сортировки Шелла: " << time_work << "cek" << endl;
}

void user_cout_mas(int *mas, size_t size)
{
    size_t d;
    cout << "Введите 0,чтобы выйти." << endl;
    cout << "Введите 1, если хотите вывести полученный массив." << endl;
    cout << "Введите 2,если не хотите выводить полученный массив." << endl;
    cin >> d;

    switch (d)
    {
        case 0: break;
        case 1:
            cout << "Ваш полученный массив:  " << endl;
            for (int i = 0; i<size; i++)
                cout << mas[i] << " ";
            cout << endl;
            break;
        case 2:
            break;
    }
}