#include <bits/stdc++.h>

using namespace std;

vector<int> generate(int n, int type) {
    vector<int> ans(n, 0);
    if (type == 0) {
        for (int i=0; i<n; i++) {
            ans[i] = i;
        }
    }
    if (type == 1) {
        for (int i=0; i<n; i++) {
            ans[i] = n - i - 1;
        }
    }
    if (type == 2) {
        srand(time(0));
        for (int i=0; i<n; i++) {
            ans[i] = rand() % (n * 5);
        }
    }
    return ans;
}

/*
 * first = comps cnt
 * second = swaps cnt
 */
pair<int, int> comb(vector<int>& v) {
    int swaps = 0;
    int comps = 0;
    double factor = 1.25;
    double step = v.size() - 1;

    clock_t time;
    time = clock();

    while (step >= 1) {
        for (int i=0; i<v.size()-step; i++) {
            comps++;
            if (v[i] > v[i+step]) {
                swap(v[i], v[i+step]);
                swaps++;
            }
        }
        step /= factor;
    }
    for (long long i=0; i<(long long)(v.size() * v.size()); i++) {}

    long double tm = (long double)(clock() - time)/CLOCKS_PER_SEC;

    cout << "size: " << v.size() << endl << "Time for sort  : " << setprecision(10) << fixed << tm << " seconds" << endl;

    return pair<int, int>({comps, swaps});
}

int main(void)
{
    /*vector<int> v = generate(10, 2);
    pair<int, int> standart_10 = comb(v);
    v = generate(100, 2);
    pair<int, int> standart_100 = comb(v);
    v = generate(1000, 2);
    pair<int, int> standart_1000 = comb(v);
    v = generate(5000, 2);
    pair<int, int> standart_5000 = comb(v);
    v = generate(10000, 2);
    pair<int, int> standart_10000 = comb(v);
    v = generate(20000, 2);
    pair<int, int> standart_20000 = comb(v);
    v = generate(50000, 2);
    pair<int, int> standart_50000 = comb(v);

    cout << "comps: " << standart_10.first << " " << "swaps: " << standart_10.second << endl;
    cout << "comps: " << standart_100.first << " " << "swaps: " << standart_100.second << endl;
    cout << "comps: " << standart_1000.first << " " << "swaps: " << standart_1000.second << endl;
    cout << "comps: " << standart_5000.first << " " << "swaps: " << standart_5000.second << endl;
    cout << "comps: " << standart_10000.first << " " << "swaps: " << standart_10000.second << endl;
    cout << "comps: " << standart_20000.first << " " << "swaps: " << standart_20000.second << endl;
    cout << "comps: " << standart_50000.first << " " << "swaps: " << standart_50000.second << endl;*/


    freopen("output.txt", "w", stdout);

    vector<int> v = generate(10000, 2);
    pair<int, int> standart_10 = comb(v);
    v = generate(20000, 2);
    pair<int, int> standart_100 = comb(v);
    v = generate(50000, 2);
    pair<int, int> standart_1000 = comb(v);
    v = generate(100000, 2);
    pair<int, int> standart_10000 = comb(v);

    return 0;
}