#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <windows.h>
#include <locale.h>

#define TEST_MASS_SIZE   5000 //количество

void task1();
void task2();
void fillArray(int* massiv, int size);
void ZeroizingMyMass(int *piMyMass);
void printArray(const int* massiv, int size, FILE* stream);
void printArray(const int* massiv, int size);
void readArray(int* massiv, int size, FILE* stream);
void copyArray(const int* src, int* dest, int size);
void SortVstavki(int *piMyMass, int iCardinality);
void SortShell(int *piMyMass, int iCardinality);
void SortSliyaniya(int *piMyMass, int iFirst, int iLast);
void vSortSl(int *piMyMass, int iFirst, int iLast);


void main(void)
{
    setlocale(0,"");
    unsigned int time1=time(NULL);
    srand(time1^(time1<<24));

    //task1();
    task2();

    system("pause");
}


void task1()
{
    int* firstArray = new int[TEST_MASS_SIZE];
    int* secondArray = new int[TEST_MASS_SIZE];
    int* thirdArray = new int[TEST_MASS_SIZE];

    fillArray(firstArray, TEST_MASS_SIZE);
    fillArray(secondArray, TEST_MASS_SIZE);
    fillArray(thirdArray, TEST_MASS_SIZE);

    printf("МАССИВЫ ДО СОРТИРОВКИ\n");
    printf("Первый масссив: \n");
    printArray(firstArray, TEST_MASS_SIZE);
    printf("Второй масссив: \n");
    printArray(secondArray, TEST_MASS_SIZE);
    printf("Третий масссив: \n");
    printArray(thirdArray, TEST_MASS_SIZE);

    FILE* beforeOut = fopen("arrays.txt", "w");
    if (beforeOut == NULL)
    {
        fprintf(stderr, "Не открывается arrays.txt");
        return;
    }
    printArray(firstArray, TEST_MASS_SIZE, beforeOut);
    printArray(secondArray, TEST_MASS_SIZE, beforeOut);
    printArray(thirdArray, TEST_MASS_SIZE, beforeOut);
    fclose(beforeOut);

    ZeroizingMyMass(firstArray);
    ZeroizingMyMass(secondArray);
    ZeroizingMyMass(thirdArray);

    FILE* in = fopen("arrays.txt", "r");
    if (in == NULL)
    {
        fprintf(stderr, "Не открывается arrays.txt");
        return;
    }
    readArray(firstArray, TEST_MASS_SIZE, in);
    readArray(secondArray, TEST_MASS_SIZE, in);
    readArray(thirdArray, TEST_MASS_SIZE, in);
    fclose(in);

    SortVstavki(firstArray, TEST_MASS_SIZE);
    SortShell(secondArray, TEST_MASS_SIZE);
    vSortSl(thirdArray, 0, TEST_MASS_SIZE-1);

    fprintf(stdout, "МАССИВЫ ПОСЛЕ СОРТИРОВКИ\n");
    fprintf(stdout, "Сортировка вставками: \n");
    printArray(firstArray, TEST_MASS_SIZE);
    fprintf(stdout, "Сортировка Шелла: \n");
    printArray(secondArray, TEST_MASS_SIZE);
    fprintf(stdout, "Сортировка слияниями: \n");
    printArray(thirdArray, TEST_MASS_SIZE);

    FILE* afterOut = fopen("sortArrays.txt", "w");
    if (afterOut == NULL)
    {
        fprintf(stderr, "Не открывается sortArrays.txt");
        return;
    }
    fprintf(afterOut, "Сортировка вставками: \n");
    printArray(firstArray, TEST_MASS_SIZE, afterOut);
    fprintf(afterOut, "Сортировка Шелла: \n");
    printArray(secondArray, TEST_MASS_SIZE, afterOut);
    fprintf(afterOut, "Сортировка слияниями: \n");
    printArray(thirdArray, TEST_MASS_SIZE, afterOut);
    fclose(afterOut);

    delete[] firstArray;
    delete[] secondArray;
    delete[] thirdArray;
}


void task2()
{
    unsigned int t1, t2, sortTime;
    int sizes[] = {8000, 16000, 32000, 64000, 128000, 256000, 512000, 700000};

    for (int i = 0; i < 8; ++i)
    {
        unsigned int minTime = 10000000000;
        unsigned int maxTime = 0;
        unsigned int sumTime = 0;

        int size = sizes[i];
        int* Mas = new int[size];
        fillArray(Mas, size);

        for (int j = 0; j < 100; ++j)
        {
            t1 = 0; t2 = 0; sortTime = 0;
            int* vstavkiSortArray = new int[size];
            copyArray(Mas, vstavkiSortArray, size);
            t1 = GetTickCount();
            SortVstavki(vstavkiSortArray, size);
            t2 = GetTickCount();
            sortTime = t2 - t1;

            if (sortTime > maxTime) {maxTime = sortTime;}
            if (sortTime < minTime) {minTime = sortTime;}
            sumTime += sortTime;

            delete[] vstavkiSortArray;
        }
        sumTime/=100;
        fprintf(stdout, "Сортировка вставками: максимум = %d минимум = %d среднее = %d\n", maxTime, minTime, sumTime);

        minTime = 10000000000; maxTime = 0; sumTime = 0;

        for (int j = 0; j < 100; ++j)
        {
            t1 = 0; t2 = 0; sortTime = 0;
            int* shellSortArray = new int[size];
            copyArray(Mas, shellSortArray, size);
            t1 = GetTickCount();
            SortShell(shellSortArray, size);
            t2 = GetTickCount();
            sortTime = t2 - t1;

            if (sortTime > maxTime) {maxTime = sortTime;}
            if (sortTime < minTime) {minTime = sortTime;}
            sumTime += sortTime;

            delete[] shellSortArray;
        }
        sumTime/=100;
        fprintf(stdout, "Сортировка     Шелла: максимум = %d минимум = %d среднее = %d\n", maxTime, minTime, sumTime);

        minTime = 10000000000; maxTime = 0; sumTime = 0;

        for (int j = 0; j < 100; ++j)
        {
            t1 = 0; t2 = 0; sortTime = 0;
            int* sliyaniyaSortArray = new int[size];
            copyArray(Mas, sliyaniyaSortArray, size);
            t1 = GetTickCount();
            vSortSl(sliyaniyaSortArray, 0, size-1);
            t2 = GetTickCount();
            sortTime = t2 - t1;

            if (sortTime > maxTime) {maxTime = sortTime;}
            if (sortTime < minTime) {minTime = sortTime;}
            sumTime += sortTime;

            delete[] sliyaniyaSortArray;
        }
        sumTime/=100;
        fprintf(stdout, "Сортировка слиянием: максимум = %d минимум = %d среднее = %d\n\n", maxTime, minTime, sumTime);

        delete[] Mas;
    }
}


void ZeroizingMyMass(int *piMyMass)
{
    for (int i=0; i<TEST_MASS_SIZE; i++) piMyMass[i]=0;
}


void fillArray(int* massiv, int size)
{
    for (int i = 0; i<size; i++)
    {
        int randomValue = rand()%21-10;
        massiv[i] = randomValue;
    }
}


void printArray(const int* massiv, int size, FILE* stream)
{
    for (int i = 0; i < size; ++i)
    {
        fprintf(stream, "%2d ", massiv[i]);
        if ((i + 1) % 10 == 0)
        {
            fprintf(stream, "\n");
        }
    }
    fprintf(stream, "\n");
}


void printArray(const int* massiv, int size)
{
    printArray(massiv, size, stdout);
}


void readArray(int* massiv, int size, FILE* stream)
{
    for (int i = 0; i < size; ++i)
    {
        fscanf(stream, "%d", massiv + i);
    }
}


void copyArray(const int* src, int* dest, int size)
{
    for (int i = 0; i < size; ++i)
    {
        dest[i] = src[i];
    }
}


void SortVstavki(int *piMyMass, int iCardinality)
{
    int tmp;
    int i,j;
    for (i=1; i < iCardinality; i++)
    {
        tmp = piMyMass[i];
        for (j=i-1; j>=0 && piMyMass[j]>tmp; j--)
            piMyMass[j+1] = piMyMass[j];
        piMyMass[j+1] = tmp;
    }
}


void SortShell(int *piMyMass, int iCardinality)
{
    int gap;
    int tmp;
    int i,j;
    for (gap = iCardinality/2; gap>0; gap/=2)
        for (i=gap; i<iCardinality; i++)
            for (j=i-gap; j>=0 && piMyMass[j] > piMyMass[j+gap]; j-=gap)
            {
                tmp = piMyMass[j];
                piMyMass[j] = piMyMass[j+gap];
                piMyMass[j+gap] = tmp;
            }
}


void SortSliyaniya(int *piMyMass, int iFirst, int iLast)
{
    int iMid, iStart, iFinish, j = 0;
    int *piNewMas = new int[iLast - iFirst + 1];
    iMid = (iFirst + iLast) / 2;                        // вычисление среднего элемента
    iStart = iFirst;                                    // начало левой части
    iFinish = iMid + 1;                                 // начало правой части
    while ((iStart <= iMid) && (iFinish <= iLast))      // идет слияние, пока есть хоть один элемент в каждой последовательности
    {
        if (piMyMass[iStart] > piMyMass[iFinish])
            piNewMas[j++] = piMyMass[iFinish++];
        else
            piNewMas[j++] = piMyMass[iStart++];
    }

    // одна последовательность закончилась - копировать остаток другой в конец буфера
    while (iFinish <= iLast)                                // пока вторая последовательность непуста
        piNewMas[j++] = piMyMass[iFinish++];
    while (iStart <= iMid)                                  // пока первая последовательность непуста
        piNewMas[j++] = piMyMass[iStart++];

    for (j = 0; j < iLast - iFirst +1; j++)                // возвращение результата в основной массив
        piMyMass[iFirst+j] = piNewMas[j];
    delete piNewMas;
}

void vSortSl(int *piMyMass, int iFirst, int iLast)
{
    if (iFirst < iLast)
    {
        vSortSl(piMyMass, iFirst, (iFirst + iLast) / 2);         // сортировка левой части
        vSortSl(piMyMass, (iFirst + iLast) / 2 + 1, iLast);      // сортировка правой части
        SortSliyaniya(piMyMass, iFirst, iLast);                       // слияние двух частей
    }
}