#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <iomanip>
#include <string>

using namespace std;
unsigned long long int c = 0;
unsigned long long int m = 0;

int compare(const void*, const void*);
void printArray(int[], int);
void inputArray(int[], int);
void put_data(int*, int);
int ShellSort(int[], int);
double timer(int*, int);


int main() {
    srand(time(NULL));
    const int n = 10;
    int a[n];
    cout << "Исходный массив " << n << " элементов: "<<endl;
    inputArray(a,n);
    cout <<endl<< "----- Тестовый прогон -----" << endl;
    ShellSort(a, n);
    cout << endl<<"Результат тестового сортировки шелла: "<<endl;
    printArray(a, n);
    cout << endl;
    cout << endl << "--------------- Контрольный Прогон ---------------" << endl;
    c = 0;
    m = 0;
    for (int i = 60000; i <= 100000; i += 10000) {
        int* work_data = new int[i];
        double time;
        put_data(work_data, i);
        cout << "---------- " << i  << " элементов ----------" << endl;
        time = timer(work_data, i);
        cout << "Средний   случай для сортировки шелла [c+m]: " << "C: "  << c << setw(12-to_string(c).length())<< "  M: " << m << " C+M: " << (c + m) << setw(12 - to_string(c + m).length()) << "  время выполнения: " << time << endl;
        c = 0;
        m = 0;
        time = timer(work_data, i);
        cout << "Наилучший случай для сортировки шелла [c+m]: " << "C: " << c << setw(12-to_string(c).length()) << "  M: " << m << "       C+M: " << (c + m) << right << setw(10) << "  время выполнения: " << time << endl;
        c = 0;
        m = 0;
        qsort(work_data, i, sizeof(int), compare);
        time = timer(work_data, i);
        cout << "Наихудший случай для сортировки шелла [c+m]: " << "C: " << c << setw(12 - to_string(c).length()) << "  M: " << m << "  C+M: " << (c + m) << setw(12 - to_string(c + m).length()) << "  время выполнения: " << time << endl;
        delete[]work_data;

    }
    _getch();
}
int compare(const void* a, const void* b)
{
    return (*(int*)b - *(int*)a);
}
void printArray(int data[], int size)
{
    for (int i = 0; i < size; ++i) {
        cout << data[i] << " ";
    }
}
void inputArray(int inputData[], int size)
{
    for (int i = 0; i < size; i++)
    {
        int x; cin >> x;
        inputData[i] = x;
    }
}
void put_data(int* data, int size)
{
    for (int i = 0; i < size; i++) {
        data[i] = rand();
    }
}
int ShellSort(int arr[], int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < n; i++)
        {
            int temp = arr[i];

            int j;
            c++;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
            {
                arr[j] = arr[j - gap];
                m++;
            }

            arr[j] = temp;
        }
    }
    return 0;
}
double timer(int* data, int size)
{
    clock_t start, end;
    double seconds;
    start = clock();
    c = 0;
    m = 0;
    ShellSort(data, size);
    end = clock();
    seconds = (double)(end - start) / CLOCKS_PER_SEC;
    return seconds;
}