#include <iostream>
#include <string>
#include <fstream>
#include <locale>
#include <stdio.h> //определения макросов, константы и объявления функций и типов, используемых для различных операций стандартного ввода и вывода
#include <time.h>
using namespace std;

void input(fstream& f, int Arr[], int sizee) {

for (int i = 0; i < sizee; i++) {
    Arr[i] = -100 + rand() % 201;
    f << Arr[i] << " ";
}
    f << endl << endl;
}

void output(fstream& f1, int Arr[], int sizee) {
    for (int i = 0; i < sizee; i++)
           f1 >> Arr[i];
}

void choice(int Arr[], int sizee) {
    for (int start = 0; start < sizee - 1; start++) {
        int max = start;
        for (int now = start + 1; now < sizee; now++) {
            if (Arr[now] > Arr[max])
                max = now;
        }
        swap(Arr[start], Arr[max]);
    }
}

double choice_time(int Arr[], int sizee) {
    clock_t start1 = clock();
    choice(Arr, sizee);
    clock_t end1 = clock();
    return ((double)end1 - start1) / (double)CLOCKS_PER_SEC;
}

double choice_time_ten(fstream& f_ch, int Arr[], int sizee) {
    double time1 = 0.0;
    for (int i = 0; i < 10; i++) {
    time1 += choice_time(Arr, sizee);
    }

    for (int i = 0; i < sizee; i++)
    f_ch << Arr[i] << " ";
    f_ch << endl << endl;


    return time1 / (double)10;
}

double sredn(int Arr[], int sizee){
    double sum = 0;
    for (int i = 0; i < sizee; i++)
            sum += Arr[i];
    return sum/sizee;
}

void fast(int Arr[], int sizee){
    int t, left = 0, right = 0;
    double x;
    x = sredn(Arr, sizee);

    int i = left;
    int j = right;

    while (i <= j) {
        while (Arr[i] < x)
            i++;
        while (Arr[j] > x)
            j--;
        if (i <= j) {
            t = Arr[i];
            Arr[i] = Arr[j];
            Arr[j] = t;
            i++;
            j--;
        }
    }
    if (i < right)
        fast(Arr, sizee);
    if (left < j)
        fast(Arr, sizee);
}

double fast_time(int Arr[], int sizee) {
    clock_t start2 = clock();
    fast(Arr, sizee);
    clock_t end2 = clock();
    return ((double)end2 - start2) / (double)CLOCKS_PER_SEC;
}

double fast_time_ten(fstream& f_fs, int Arr[], int sizee) {
    double time2 = 0.0;
    for (int i = 0; i < 10; i++) {
        time2 += fast_time(Arr, sizee);
    }
    for (int i = 0; i < sizee; i++)
    f_fs << Arr[i] << " ";
    f_fs << endl << endl;

    return time2 / (double)10;
}

void shell(int Arr[],int sizee){
    int i, j, n = 0, d,count;
    d = n;
    d = d/2;
    while(d > 0) {
        for (i = 0; i < n - d; i++) {
            j = i;
            while (j >= 0 && Arr[j] > Arr[j + d]) {
                count = Arr[j];
                Arr[j] = Arr[j + d];
                Arr[j + d] = count;
                j--;
            }
        }
        d = d/2;
    }
}

double shell_time(int Arr[], int sizee) {
    clock_t start3 = clock();
    shell(Arr, sizee);
    clock_t end3 = clock();
    return ((double)end3 - start3) / (double)CLOCKS_PER_SEC;
}

double shell_time_ten(fstream& f_sh, int Arr[], int sizee) {
    double time3 = 0.0;
    for (int i = 0; i < 10; i++) {
        time3 += shell_time(Arr, sizee);
    }
    for (int i = 0; i < sizee; i++)
    f_sh << Arr[i] << " ";
    f_sh << endl << endl;

    return time3 / (double)10;
}

int main() {
    setlocale(0, "");

    fstream f_ch("choice.txt", ios::out);
    fstream f_fs("fast.txt", ios::out);
    fstream f_sh("shell.txt", ios::out);

    int size1 = 100, size2 = 1000, size3 = 5000, size4 = 10000, size5 = 50000, size6 = 100000;
    int randArr1[size1], randArr2[size2], randArr3[size3], randArr4[size4], randArr5[size5], randArr6[size6];
    int Arr1[size1], Arr2[size2], Arr3[size3], Arr4[size4], Arr5[size5], Arr6[size6];

    fstream f("result.txt", ios::out);

    input(f, randArr1, size1);
    input(f, randArr2, size2);
    input(f, randArr3, size3);
    input(f, randArr4, size4);
    input(f, randArr5, size5);
    input(f, randArr6, size6);

    f << endl << endl;

    fstream f1("result.txt");
    if (!f.is_open()) // если файл не открыт
        cout << "Файл не может быть открыт! " << endl; // сообщить об этом
    else{
        cout << "Файл открыт! " << endl;;
    }

    output(f1, Arr1, size1);
    output(f1, Arr2, size2);
    output(f1, Arr3, size3);
    output(f1, Arr4, size4);
    output(f1, Arr5, size5);
    output(f1, Arr6, size6);

    cout << endl;

    cout << "Массив №1 (100) || алгоритм Выбора || Среднее время = " << choice_time_ten(f_ch, Arr1, size1) << endl;
    cout << "Массив №1 (100) || алгоритм Быстрой сортировки || Среднее время = " << fast_time_ten(f_fs, Arr1, size1) << endl;
    cout << "Массив №1 (100) || алгоритм Шелла || Среднее время = " << shell_time_ten(f_sh, Arr1, size1) << endl << endl;


    cout << "Массив №2 (1000) || алгоритм Выбора || Среднее время = " << choice_time_ten(f_ch, Arr2, size2) << endl;
    cout << "Массив №2 (1000) || алгоритм Быстрой сортировки || Среднее время = " << fast_time_ten(f_fs, Arr2, size2) << endl;
    cout << "Массив №2 (1000) || алгоритм Шелла || Среднее время = " << shell_time_ten(f_sh, Arr2, size2) << endl << endl;


    cout << "Массив №3 (5000) || алгоритм Выбора || Среднее время = " << choice_time_ten(f_ch, Arr3, size3) << endl;
    cout << "Массив №3 (5000) || алгоритм Быстрой сортировки || Среднее время = " << fast_time_ten(f_fs, Arr3, size3) << endl;
    cout << "Массив №3 (5000) || алгоритм Шелла || Среднее время = " << shell_time_ten(f_sh, Arr3, size3) << endl << endl;


    cout << "Массив №4 (10000) || алгоритм Выбора || Среднее время = " << choice_time_ten(f_ch, Arr4, size4) << endl;
    cout << "Массив №4 (10000) || алгоритм Быстрой сортировки || Среднее время = " << fast_time_ten(f_fs, Arr4, size4) << endl;
    cout << "Массив №4 (10000) || алгоритм Шелла || Среднее время = " << shell_time_ten(f_sh, Arr4, size4) << endl << endl;


    cout << "Массив №5 (50000) || алгоритм Выбора || Среднее время = " << choice_time_ten(f_ch, Arr5, size5) << endl;
    cout << "Массив №5 (50000) || алгоритм Быстрой сортировки || Среднее время = " << fast_time_ten(f_fs, Arr5, size5) << endl;
    cout << "Массив №5 (50000) || алгоритм Шелла || Среднее время = " << shell_time_ten(f_sh, Arr5, size5) << endl << endl;


    cout << "Массив №6 (100000) || алгоритм Выбора || Среднее время = " << choice_time_ten(f_ch, Arr6, size6) << endl;
    cout << "Массив №6 (100000) || алгоритм Быстрой сортировки || Среднее время = " << fast_time_ten(f_fs, Arr6, size6) << endl;
    cout << "Массив №6 (100000) || алгоритм Шелла || Среднее время = " << shell_time_ten(f_sh, Arr6, size6) << endl;

    f.close();
    f1.close();
    f_ch.close();
    f_fs.close();
    f_sh.close();
    return 0;
}