#include "stdafx.h"
#include <windows.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include<conio.h>
#define MAX_LEN 10000
int arrgen(int n, int *arr)
{
    for (int i = 0; i < n; i++)
    {
        arr[i] = rand() % (100 - 50 + 1) + 50;
    }
    return *arr;
}
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    srand(time(NULL));
    int choice, menu, a, b, amount, rndArray[MAX_LEN], N = 3000;
    time_t point1, point2, point3;
    double d;
    printf("1. Продолжить работу.\n");
    printf("2. Завершить работу.\n");
    printf("Выберите: "); scanf_s("%d", &choice);
    printf("Количество: "); scanf_s("%d", &amount);
    int n1 = amount;
    printf("\n1. Сортировка пузырьком\n");
    printf("2. Сортировка обменом\n");
    printf("3. Сортировка вставками\n");
    printf("4. Сортировка Шелла\n");
    switch (choice)
    {
    case 1:
        printf("\n0 - завершает программу");
        do {
            printf("\n\nВаш выбор: ");
            scanf_s("%d", &menu);
            switch (menu)
            {
            case 0: printf("Вы покидаете программу."); break;
            case 1:
                point1 = time(NULL);
                for (int i = 0; i < N; i++)
                {
                    rndArray[amount] = arrgen(amount, rndArray);
                }
                int tmp, is;
                point2 = time(NULL);
                for (int k = 0; k < N; k++)
                {
                    rndArray[amount] = arrgen(amount, rndArray);
                    do {
                        is = 0;
                        for (int i = 0; i < n1 - 1; i++)
                            if (rndArray[i] > rndArray[i + 1])
                            {
                                tmp = rndArray[i];
                                rndArray[i] = rndArray[i + 1];
                                rndArray[i + 1] = tmp;
                                is = 1;
                            }
                        n1--;
                    } while (is);
                }
                point3 = time(NULL);
                d = (double)((point3 - point2) - (point2 - point1)) / N;
                printf("Время сотировки %f", d);
                break;
            case 2:
                point1 = time(NULL);
                for (int i = 0; i < N; i++)
                {
                    rndArray[amount] = arrgen(amount, rndArray);
                }
                int tmp1, jmin;
                point2 = time(NULL);
                for (int k = 0; k < N; k++)
                {
                    for (int j = 0; j < amount - 1; j++)
                    {
                        jmin = j;
                        for (int i = j + 1; i < amount; i++)
                            if (rndArray[i] < rndArray[jmin]) jmin = i;
                        tmp1 = rndArray[j];
                        rndArray[j] = rndArray[jmin];
                        rndArray[jmin] = tmp1;
                    }
                }
                point3 = time(NULL);
                d = (double)((point3 - point2) - (point2 - point1)) / N;
                printf("Время сортировки: %f", d);
                break;
            case 3:
                point1 = time(NULL);
                for (int i = 0; i < N; i++)
                {
                    rndArray[amount] = arrgen(amount, rndArray);
                }
                int tmp2, i, j;
                point2 = time(NULL);
                for (int k = 0; k < N; k++)
                {
                    for (j = 1; j < amount; j++)
                    {
                        tmp2 = rndArray[j];
                        for (i = j - 1; i >= 0 && rndArray[i] > tmp2; i--)
                        {
                            rndArray[i + 1] = rndArray[i];
                            rndArray[i] = tmp2;
                        }
                    }
                }
                point3 = time(NULL);
                d = (double)((point3 - point2) - (point2 - point1)) / N;
                printf("Время сортировки: %f", d);
                break;
            case 4:
                point1 = time(NULL);
                for (int i = 0; i < N; i++)
                {
                    rndArray[amount] = arrgen(amount, rndArray);
                }
                int tmp4;
                point2 = time(NULL);
                for (int k = 0; k < N; k++)
                {
                    rndArray[amount] = arrgen(amount, rndArray);
                    int arr2[100];
                    arr2[0] = 1;
                    int i;
                    for (i = 1; i < 1000; i++)
                    {
                        if (3 * arr2[i - 1] > amount)
                            break;
                        if (i % 2 == 0)
                            arr2[i] = 9 * pow(2, i) - 9 * pow(2, i / 2) + 1;
                        else
                            arr2[i] = 8 * pow(2, i) - 6 * pow(2, (i + 1) / 2) + 1;
                    }
                    int step = arr2[i];
                    int j;
                    while (step > 0)
                    {
                        i--;
                        j = 0;
                        for (j; j < (amount - step); j++)
                        {
                            int l = j;
                            while (l >= 0 && rndArray[l] > rndArray[l + step])
                            {
                                int tmp = rndArray[l];
                                rndArray[l] = rndArray[l + step];
                                rndArray[l + step] = tmp;
                                l--;
                            }
                        }
                        step = rndArray[i];
                    }
                }
                point3 = time(NULL);
                d = (double)((point3 - point2) - (point2 - point1)) / N;
                printf("Время сортировки: %f", d);
                break;
            default: printf("Выберете другой пункт.\n");
            }
        } while (menu != 0); break;
    case 2: printf("Вы покидаете программу"); break;
    default: printf("Вы ошиблись в выборе.\n");
    }
    return 0;
}