Strona główna

Algorytmy sortowania Grzegorz Kupiec


Pobieranie 20.41 Kb.
Data18.06.2016
Rozmiar20.41 Kb.
30.03.2011

PAMSI

Algorytmy sortowania

Grzegorz Kupiec

Środa godz. 16-19

Sprawozdanie przedstawia sposoby sortowania danych za pomocą różnych algorytmów i oceny ich efektywności. Wykorzystywane są w celu uporządkowania danych. Wszystkie liczby użyte podczas testów były losowe. Przeanalizowane algorytmy:


Przedstawione zostaną pokrótce poszczególne algorytmy sortowania oraz porównanie ich działań na wykresach.

  1. Sortowanie bąbelkowe

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany, przez co jego teoretyczna złożoność czasowa wynosi O(n^2). Istnieją różne wersje tego sortowania, które optymalizują czas działania, ale prezentowana w sprawozdaniu wersja jest najprostrza, bez żadnych ulepszeń. Algorytm wygląda tak:

Rys. 1 Algortym sortowania bąbelkowego

Przykład działania jest z kolei następujący:



  1. Sortowanie przez kopcowanie

Algorytm sortowania przez kopcowanie składa się z dwóch faz. W pierwszej sortowane elementy reorganizowane są w celu utworzenia kopca. W drugiej zaś dokonywane jest właściwe sortowanie. Złożoność czasowa jest równa О(n log(n)).

  1. Struktura danych jest oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica, na przykład wartość rodzica jest nie mniejsza niż wartości jego potomka. Drzewo binarne jest hierarchiczną strukturą danych, w której każde dziecko może posiadać co najwyżej jednego rodzica. W drzewie binarnym każdy rodzic może posiadać dwoje potomków (stąd pochodzi nazwa drzewa - binarny = dwójkowy). Przykład wierzchołka drzewa, w którym na szczycie jest tylko rodzic posiadający dwoje potomków, z których każde posiada kolejne dwoje dzieci.

Algorytm działania jest następujący:



Rys. 2 Algortym sortowania przez kopcowanie

Po utworzeniu kopca następuje właściwe sortowanie. Polega ono na usunięciu wierzchołka kopca, zawierającego element maksymalny lub minimalny, a następnie wstawieniu w jego miejsce elementu z końca kopca i odtworzenie porządku kopcowego. W zwolnione w ten sposób miejsce, zaraz za końcem zmniejszonego kopca wstawia się usunięty element maksymalny. Operacje te powtarza się aż do wyczerpania elementów w kopcu.


  1. Sortowanie przez wstawianie

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą. Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce, stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, Jeśli nasza karta jest najstarsza , to umieszczamy ją na samym końcu. Algorytm sortowania przez wstawianie posiada klasę czasowej złożoności obliczeniowej równą O(n^2). Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy kopcowanie to posiada pewne zalety:

  • jest wydajny dla danych wstępnie posortowanych

  • jest wydajny dla zbiorów o niewielkiej liczebności

Schemat blokowy jest następujący:

Rys. 3 Algortym sortowania przez wstawianie



  1. Sortowanie szybkie

W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(n log n) - stąd pochodzi jego popularność w zastosowaniach. Trzeba zwrócić natomiast uwagę na to, że złożonośc obliczeniowa tego algorytmu może się degradować do O(n2), co więcej, poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera. Może się to wydarzyć, jeśli niekorzystnie wybierzemy liczbę z końca listy lub dane wejściowe będą po prostu nieprzychylne, przez co nie będzie możliwe podzielenie problemu na mniejsze, w którym to właśnie celu powstało te sortowanie.

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj", którą możemy krótko scharakteryzować w trzech punktach:

DZIEL - Problem główny zostaje podzielony na podproblemy. Najpierw sortowany zbiór dzielimy na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją).

ZWYCIĘŻAJ - Znajdujemy rozwiązanie podproblemów. Każdą z partycji sortujemy rekurencyjnie tym samym algorytmem.

POŁĄCZ - Rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego. Połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany.

Algorytm ma następujący schemat blokowy:



Rys. 4 Algortym sortowania szybkiego

Sortowania szybkiego nie można stosować zawsze i wszędzie tylko dlatego, że jest powszechnie uważany za najszybszy. Często lepiej sprawdzić dane wejściowe pod kątem niekorzystych np. liczb, więc najpewniejszym sposobem rozwiązywania problemów sortujących jest użycie wcześniejszego algorytmu sortowania przez kopcowanie.


  1. Porównanie algorytmów sortowania.

Przedstawione poniżej wykresy obrazują czas obliczeniowy dla posortowania różnych liczb. Niestety kompilator wykazywał niechęć do współpracy oraz lenistwo, czego efektem była niemożliwość operowania na liczbach większych niż 20 tys. dla sortowań bąbelkowych i przez wstawianie oraz 500 tys. dla pozostałych dwóch algorytmów. Przyczyny nie mogłem znaleźć, na innych kompilatorach jest ten sam efekt nawet wykorzystując różne kody źródłowe.

Na poniższym wykresie możemy zauważyć, że sortowanie przez wstawianie jest szybsze od bąbelkowego, niestety jak już napisałem wcześniej, nie mogłem przeprowadzić porównania dla większych liczb.



Rys. 5 Prównanie sortowania bąbelkowego i przez wstawianie

Prezentowany kolejny wykres obrazuje czas sortowania dla ostatnich dwóch algorytmów.

Rys. 6 Prównanie sortowania szybkiego i przez kopcowanie

Przedstawiony poniżej wykres pokazuje wszystkie cztery algorytmy.

Rys. 7 Prównanie wszystkich czterech algorytmów

Niestety jak już wcześniej zostało napisane, nie można było przeprowadzić dokładych pomiarów czasowych ze względu na brak współpracy kompilatora. Jednakże można wywnioskować, że sortowanie szybkie jest jak sama nazwa wskazuje najszybsze, ale tylko na próbie 500 tys. elementów. Nie wiemy do końca jak zachowywałby się wykres dla większych liczb. Zwrócić uwagę może również to, że w każdym przypadku użycie pamięci operacyjnej było na poziomie 2 MB, najmniejsze natomiast w sortowaniu szybkim.

W ramach rekompensaty przedstawię algorytm sortowania przez kopcowanie, który został napisany przeze mnie na laboratorium. Niby wszystko się zgadza, działanie nie powodowało żadnych podejrzeń, jednak przy próbie kompilowania go w domowych warunkach okazało się coś dziwnego. Mianowicie owe sortowanie powinno działać bardzo szybko, natomiast okazało się najwolniejsze i pochłaniało niesamowite zasoby pamięciowe. Górną granicą wydajności systemu okazało się 20 tys., ponieważ zabrakło już pamięci. Czas też był zadziwiająco długi, ponad 11 sekund. Nie znam przyczyny takiego zachowania, ponieważ nie mogłem znaleźć błędu. Użycie pamięci RAM dla tego przypadku wyniosło ponad 1,8 GB.





©snauka.pl 2016
wyślij wiadomość