Raport z projektu
Przedmiot: Algorytmy i złożoność
Autor: Kamil Adamuszek
Projekt: Sortowanie Shell’a
Raport z projektu
Przedmiot: Algorytmy i złożoność
Autor: Kamil Adamuszek
Projekt: Sortowanie Shell’a
1. Zadanie
Przetestować różne metody sortowania Shella za pomocą różnych
ciągów. Ciągi do testów:
a) 𝑎
𝑛
=
8∗𝑘−5
20
b) 𝑎
𝑛
= 2
𝑘
− 1 złożoność O(𝑛
3
2
)
c) 𝑎
𝑛
= 𝑘
1
2
+ 1
d) 𝑎
𝑛
= 𝑘
2
− 1
e) 𝑎
𝑛
= 1
𝑘
+ 𝑘
f) 𝑎
𝑛
= 2
3𝑘
4
− 1
g) 𝑎
𝑛
= 𝑘
4
− 1
h) 𝑎
𝑛
= 𝑘
7
+ 61
i) 𝑎
𝑛
= 4
𝑘
+ 3 ∗ 2
𝑘−1
+ 1 złożoność O(𝑛
4
3
)
j)
𝑎
𝑛
=
złożoność O(𝑛
2
)
2. Opis sortowania Shella.
W latach 50-tych ubiegłego wieku informatyk Donald Shell zauważył, iż
algorytm sortowania przez wstawianie pracuje bardzo efektywnie w
przypadku, gdy zbiór jest w dużym stopniu uporządkowany (sprawdź
wyniki naszych badań czasów sortowania dla tego algorytmu). Z kolei
algorytm ten pracuje nieefektywnie w zbiorach nieuporządkowanych,
ponieważ elementy są przesuwane w każdym obiegu o jedną pozycję przy
wstawianiu elementu wybranego na listę uporządkowaną.
Pomysł Shella polegał na tym, iż sortowany zbiór dzielimy na podzbiory,
których elementy są odległe od siebie w sortowanym zbiorze o pewien
odstęp h. Każdy z tych podzbiorów sortujemy algorytmem przez
wstawianie. Następnie odstęp zmniejszamy. Powoduje to powstanie
nowych podzbiorów (będzie ich już mniej). Sortowanie powtarzamy i
znów zmniejszamy odstęp, aż osiągnie on wartość 1. Wtedy sortujemy już
normalnie za pomocą Insert Sort. Jednakże z uwagi na wcześniejsze obiegi
sortujące mamy ułatwione zadanie, ponieważ zbiór został w dużym
stopniu uporządkowany. Dzięki początkowym dużym odstępom elementy
były przesuwane w zbiorze bardziej efektywnie - na duże odległości. W
wyniku otrzymujemy najlepszy pod względem szybkości czasu wykonania
algorytm sortujący w klasie O(n
2
).Algorytm ten nosi również nazwę
algorytmu sortowania
przez
wstawianie
z
malejącym
odstępem (ang. Diminishing Increment Sort).
Efektywność algorytmu sortowania metodą Shella zależy w dużym stopniu
od ciągu przyjętych odstępów. Pierwotnie Shell proponował pierwszy
odstęp równy połowie liczby elementów w sortowanym zbiorze. Kolejne
odstępy
otrzymujemy
dzieląc
odstęp
przez
2 (dzielenie
całkowitoliczbowe).
3. Kod programu
#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;
}
4. 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
0
50
100
150
200
250
300
350
400
450
C
zas
w
m
s
Ilość wyników
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
0
50
100
150
200
250
300
350
400
450
C
zas
w
m
s
Ilość wyników
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
0
50
100
150
200
250
300
350
400
450
C
zas
w
m
s
Ilość wyników
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
0
50
100
150
200
250
300
C
Zas
w
ms
Ilość wyników
wykres h
wykres g
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
0
50
100
150
200
250
300
350
C
Zas
w
ms
Ilość wyników
wykres j
wykres i
5. Wnioski
15
32
63
79
94
125
140
157
187
203
234
266
282
296
312
344
359 359
375
406
16
32
46 47
62
78
93 94
125
141
157 157
172
187
203
218
250 250
266
281
10
20
32
43
54
68
81
93
106
115
130
146
156
172
181
199
210
218
234
248
8
14
24
31
41
52 57
66
77
88
99
109
117
128
138
146 152
161
172
179
15 16
31
46
62
78
94
109 110
125
140
157
172
188
204
219
234
250
266
281
16
31
47
62
78
94 94
110
125
141
157
172
187 188
203
235
250
266
281
297
16
31 32
46
63
78
93
109
125
140
157 157
172
188
203
234 234
266 266
281
15 15
31
47
62
78
93
110
125
140
156 157
172
188
203
234 234
266 266
281
11
25
39
65
75
93
109
125
143
157
178 180
194
208
240
259
290 291
313
335
12
30
37
51
66
92
100
111
127
145
167
175
214 216
223
247
283
307
321
334
-40
10
60
110
160
210
260
310
360
410
Porównanie
wykres e
wykres f
wykres a
wykres b
wykres c
wykres d
wykres g
wykres h
wykres i
wykres j