#include <cmath>

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

int main()

{

int h,i,j,x,N;

int *d=0;

cout << endl << "Podaj ilosc elementow tablicy: ";

cin >> N;

d=new int[N-1];

d[N-1]=1;

cout <<"Przed sortowaniem:\n\n";

for(i = 1; i <N; i++)

d[N-i-1] =pow(2,i)-1;

//for(i = 0; i<N ; i++) cout << d[i]<<"\n";

//cout << endl;

// Wyznaczamy wartosc poczatkowego przesuniecia

for(h = 1; h < N; h = 3 * h + 1);

h /= 9;

// Sortujemy

clock_t start, stop;

start = clock();

while(h)

{

for(j = N - h - 1; j >= 0; j--)

{

x = d[j];

i = j + h;

while((i < N) && (x > d[i]))

{

d[i - h] = d[i];

i += h;

}

d[i - h] = x;

}

h /= 3;

}

stop = clock();

cout.precision(20);

//cout << "Po sortowaniu:\n\n";

//for(i = 0; i < N; i++) {cout <<d[i]<<"\n";

//}

cout << "Czas w [ms] = " << stop-start<<"\n";

return 0;

}

1. Testy

Ilość wyników	Ciąg a	Ciąg b
50000	10	8
100000	20	14
150000	32	24
200000	43	31
250000	54	41
300000	68	52
350000	81	57
400000	93	66
450000	106	77
500000	115	88
550000	130	99
600000	146	109
650000	156	117
700000	172	128
750000	181	138
800000	199	146
850000	210	152
900000	218	161
950000	234	172
1000000	248	179

Ilość wyników	Ciąg c	Ciąg d
50000	15	16
100000	16	31
150000	31	47
200000	46	62
250000	62	78
300000	78	94
350000	94	94
400000	109	110
450000	110	125
500000	125	141
550000	140	157
600000	157	172
650000	172	187
700000	188	188
750000	204	203
800000	219	235
850000	234	250
900000	250	266
950000	266	281
1000000	281	297

Ilość wyników	Ciąg e	Ciąg f
50000	15	16
100000	32	32
150000	63	46
200000	79	47
250000	94	62
300000	125	78
350000	140	93
400000	157	94
450000	187	125
500000	203	141
550000	234	157
600000	266	157
650000	282	172
700000	296	187
750000	312	203
800000	344	218
850000	359	250
900000	359	250
950000	375	266
1000000	406	281

Ilość wyników	Ciąg g	Ciąg h
50000	16	15
100000	31	15
150000	32	31
200000	46	47
250000	63	62
300000	78	78
350000	93	93
400000	109	110
450000	125	125
500000	140	140
550000	157	156
600000	157	157
650000	172	172
700000	188	188
750000	203	203
800000	234	234
850000	234	234
900000	266	266
950000	266	266
1000000	281	281

Ilość wyników	Ciąg i	Ciąg j
50000	11	12
100000	25	30
150000	39	37
200000	65	51
250000	75	66
300000	93	92
350000	109	100
400000	125	111
450000	143	127
500000	157	145
550000	178	167
600000	180	175
650000	194	214
700000	208	216
750000	240	223
800000	259	247
850000	290	283
900000	291	307
950000	313	321
1000000	335	334

1. Wnioski