Konrad Kukulski, 163930                                                                                    Wrocław, 28.04.2010

Elżbieta Tchorowska, 171067

Struktury danych i złożoność obliczeniowa

Projekt nr 1

Temat: Badanie efektywności algorytmów sortowania w zależności od liczby sortowanych elementów.

Prowadzący: prof. dr hab. inż. A. Janiak

Spis treści:

Spis treści:              2

Plan doświadczenia              3

Sortowanie bąbelkowe              3

Cechy algorytmu              3

Wyniki doświadczenia              3

dla danych posortowanych              3

dla danych posortowanych odwrotnie              4

dla danych losowych              5

Ocena algorytmu              5

Sortowanie przez kopcowanie              5

Cechy algorytmu              5

Wyniki doświadczenia              6

dla danych posortowanych              6

dla danych posortowanych odwrotnie              6

dla danych losowych              7

Ocena algorytmu              8

Sortowanie kubełkowe              8

Cechy algorytmu              8

Wyniki doświadczenia              8

dla danych posortowanych              8

dla danych posortowanych odwrotnie              9

dla danych losowych              9

Ocena algorytmu:              10

Sortowanie przez scalanie              10

Cechy algorytmu              10

Wyniki doświadczenia              11

dla danych posortowanych              11

dla danych posortowanych odwrotnie              11

dla danych losowych              12

Ocena algorytmu              13

Sortowanie szybkie              13

Cechy algorytmu              13

Wyniki doświadczenia              13

dla danych posortowanych              13

dla danych posortowanych odwrotnie              14

dla danych losowych              14

Ocena algorytmu              15

Sortowanie metodą Shella              15

Cechy algorytmu              15

Wyniki doświadczenia              15

dla danych posortowanych              15

dla danych posortowanych odwrotnie              16

dla danych losowych              16

Ocena algorytmu              17

Wnioski              17

Plan doświadczenia

              Do przeprowadzenia doświadczenia użyto komputera z procesorem Intel Core Duo 1,86GHz, 1 Gb RAM. Językiem programowania, który posłużył do napisania algorytmów sortujących był C++, pod środowiskiem Dev-C++.

              Pomiar czasu sortowań wykonywany był z poziomu programu, nie kompilatora. Szczegółowy rozkład n liczb sortowanych przedstawiał się: 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 10.000, 12.000, 14.000, 16.000, 20.000, 25.000, 32.000, 48.000, 64.000, 100.000, 200.000, 300.000, 400.000, 500.000. Sortowano dla liczb z przedziału (1000-500.000) co 1000 (z wyjątkiem sortowania bąbelkowego). Sortowania były przeprowadzane w trzech przypadkach: elementów posortowanych, posortowanych odwrotnie i ustawionych losowo.

Sortowanie bąbelkowe

Cechy algorytmu

·         Optymistyczna klasa złożoności obliczeniowej: O(n)

·         Pesymistyczna klasa złożoności obliczeniowej : O(

·         Typowa klasa złożoności obliczeniowej: O(

Wyniki doświadczenia

dla danych posortowanych

Wykres:

dla danych posortowanych odwrotnie

Wykres:

dla danych losowych

Wykres:

Ocena algorytmu

Algorytm sortowania bąbelkowego jest najdłuższy dla danych losowych, w tym wypadku najkrótszy dla danych już posortowanych. Sortowanie bąbelkowe jest najmniej optymalnym algorytmem, nie używanym do dużych n.

Sortowanie przez kopcowanie

Cechy algorytmu

·         Optymistyczna klasa złożoności obliczeniowej: O(n*log(n))

·         Pesymistyczna klasa złożoności obliczeniowej : O(n*log(n))

·         Typowa klasa złożoności obliczeniowej: O(n*log(n))

Wyniki doświadczenia

dla danych posortowanych

Wykres:

Wnioski:

dla danych posortowanych odwrotnie

Wykres:

 ...