#include <iostream>
#include <time.h>
#include <string>
#include <vector>

using namespace std;

int main() {
    std::cout << "Hello, World!" << std::endl;
    int n = 10000000;
    int c[] = {510774, 227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1};
    string *v;
    v = new string[n];
    for (int i = 0; i < n; i++) {
        v[i] = rand() % 57 + 65;
    }
    string temp;
    int gap;
    clock_t t =  clock();
    clock_t  clock1,clock2;
    clock1 = clock();
    int k = 0;
    for( int x = 0; x < 16; ++x ){
    gap = c[x];
    //for (gap = 2 * (n / 4 ) + 1; gap > 0; gap /= 2 + 1) {
        for(int i = gap; i < n; i++) {
            for(int j  = i - gap; j >= 0 && v[j] > v[j + gap]; j-=gap) {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }

    clock2 = clock();
    std::cout<< "Shell time "<< (float)(clock2 - clock1)/ CLOCKS_PER_SEC << " "<< std::endl;;



    return 0;
}