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