|
Sortowanie jest jednym z najczęściej rozwiązywanych problemów informatycznych. Według różnych autorów, komputery spędzają od 25 do 80 procent czasu na porządkowaniu informacji. Porządek wśród elementów ułatwia i przyspiesza wykonywanie innych operacji (np. przeszukiwania).
Sortowanie jest też przykładem problemu, który może być rozwiązany na wiele sposobów, a ich efektywność jest istotnie różna. Za efektywność algorytmów sortujących przyjmuje się liczbę porównań wykonywanych między elementami danych. Zwykle jest ona podawana jako zależność od liczby elementów do uporządkowania.
Problem sortowania można zdefiniować następująco : danymi wejściowymi jest jakiś ciąg n liczb. Wynikiem zaś sortowania jest taka ich zmiana kolejności, że utworzą one ciąg rosnący (niemalejący), czyli od najmniejszego do największego.
Zadaniem każdego algorytmu sortowania jest więc takie przestawienie elementów danego ciągu, aby były one uporządkowane rosnąco.
Sortowanie bąbelkowe
Algorytm sortowania bąbelkowego polega na porównywaniu par elementów leżących obok siebie i, jeśli jest to potrzebne, zmienianiu ich kolejności.
Każdy element jest tak długo przesuwany w ciągu, aż napotkany zostanie element większy od niego, wtedy w następnych krokach przesuwany jest ten większy element.
Po pierwszym przebiegu ciąg nie musi być jeszcze uporządkowany, ale na pozycji n znajdzie się maksymalny element ciągu. Zatem w drugim przebiegu można porządkować ciąg krótszy, czyli tylko elementy na pozycjach od 1 do n-1. Po drugim przebiegu, dwa ostatnie elementy są na swoich miejscach, czyli pozostaje posortować ciąg o dwa elementy krótszy, itd.
Sortowanie przez wstawiania
W algorytmie sortowania przez wstawianie ciąg danych jest dzielony na dwie części : już uporządkowaną (przed uruchomieniem procedury nie zawiera ona żadnych elementów),i jeszcze nie uporządkowaną (na początku zawiera wszystkie elementy).
Sposób porządkowania można opisać następująco :
weź pierwszy element z części nieuporządkowanej (jeśli jest pusta to zakończ działanie algorytmu), wstaw go w odpowiednie miejsce w części uporządkowanej (po takiej operacji część nieuporządkowana jest jeden element krótsza, a część posortowana zyskuje jeden element).
Pozostaje jeszcze do rozstrzygnięcia, w jaki sposób wyznaczyć prawidłowe położenie nowego elementu w części uporządkowanej. Najprostszy sposób polega na porównaniu tego elementu z kolejnymi elementami części uporządkowanej. Jeżeli element na pozycji i jest większy od wstawianego, to ten nowy element należy wstawić między elementy na pozycjach i-1 i i.
Sortowanie przez wybór
Jest to najbardziej intuicyjny algorytm sortowania. Polega on na wielokrotnym wyborze minimalnego elementu z coraz krótszego podciągu danych.
Dokładnie ma to następujący przebieg :
- Wybierz minimum z ciągu elementów na pozycjach od 1 do n i zamień go z pierwszym elementem.
- Wybierz minimum z ciągu elementów na pozycjach od 2 do n i zamień go z drugim elementem (po tym kroku elementy na pozycjach od 1 do 2 są uporządkowane).
- ...
- Wybierz minimum z ciągu elementów na pozycjach n-1 i n i zamień go z elementem na pozycji n-1 (po tej operacji elementy na pozycjach od 1 do n-1 są uporządkowane, a element na pozycji n jest maksymalny, czyli ciąg elementów na pozycjach od 1 do n jest uporządkowany)
Znalezienie minimum w ciągu wymaga m-1 porównań, gdzie m jest długością ciągu. Algorytm sortowania przez wybór wykonuje n-1 takich operacji, a długość ciągu, z którego wybierany jest element minimalny zmienia się od n do 2.
Sortowanie przez scalanie
W algorytmie sortowania przez scalanie jest wykorzystywana strategia "dziel i zwyciężaj", podobnie jak w sortowaniu "szybkim".
Wyobraźmy sobie, że mamy dwa uporządkowane ciągi, a chcemy utworzyć z nich jeden - także uporządkowany. Można oczywiście potraktować je jako jeden ciąg i posortować jedną ze znanych metod, ale nie zostanie wykorzystane uporządkowanie obu ciągów.
Warto zastosować następujący sposób :
- Porównujemy ze sobą pierwsze elementy z każdego z ciągów danych.
- Mniejszy element wstawiamy do nowego ciągu i usuwamy z ciągu danych.
- Powtarzamy te czynności, aż oba ciągi danych będą puste.
W ten sposób, w nowo utworzonym ciągu wszystkie elementy są uporządkowane, a co najważniejsze operacja ta wymaga wykonania niewielu porównań.
Wiadomo już, jak z dwóch uporządkowanych ciągów otrzymać jeden. Wykorzystując to, można sformułować algorytm sortowania dowolnego ciągu :
- Podziel ciąg na dwie równe części (jeśli ciąg ma nieparzystą liczbę elementów, jedna z części będzie miała o jeden element więcej).
- Każdą z części uporządkuj.
- Połącz dwa uporządkowane ciągi w jeden ciąg uporządkowany.
Pozostaje jeszcze rozstrzygnąć, w jaki sposób posortować każdy z dwóch podciągów? W odpowiedzi zawiera się cała siła tego algorytmu: w ten sam sposób! Po prostu wywołujemy rekurencyjnie ten sam algorytm dla każdego z podciągów. Aby takie postępowanie nie przebiegało w nieskończoność należy określić, kiedy zaprzestajemy podziału ciągu. Następuje to, gdy sortowany ciąg ma mniej niż dwa elementy.
Ostatecznie algorytm ma następującą postać :
- Jeśli ciąg zawiera więcej niż jeden element, to podziel go na dwie równe części (lub prawie równe, jeśli ciąg ma nieparzystą liczbę elementów).
- Posortuj pierwszą część stosując ten sam algorytm.
- Posortuj drugą część stosując ten sam algorytm.
- Połącz dwa uporządkowane ciągi w jeden ciąg uporządkowany.
Sortowanie "szybkie"
Przypuśćmy, że potrafimy podzielić dany ciąg na dwie takie części, że elementy pierwszego ciągu są mniejsze od elementów drugiego ciągu, czyli nieformalnie mówiąc, na elementy "małe" i "duże". Mając taki podział ciągu, możemy każdą z części uporządkować osobno (pomińmy na razie, w jaki sposób to zrobić). Otrzymamy ciąg składający się z uporządkowanych elementów "małych", a po nich następują uporządkowane elementy "duże" - czyli cały ciąg jest już uporządkowany !
Algorytm służący do dzielenia ciągu na dwie części, spełniające opisany warunek, ma następującą postać:
- Weź pierwszy element ciągu (oznaczmy go przez x).
- Podziel ciąg tak, aby w pierwszej części znalazły się elementy mniejsze lub równe x, a w drugiej większe lub równe x
Można teraz podać pełny algorytm sortujący:
- Jeżeli liczba elementów w ciągu jest większa od 1, to podziel ciąg na dwie części tak, aby elementy z pierwszej części były nie większe niż elementy z drugiej części.
- Wywołaj procedurę sortującą dla pierwszej części ciągu.
- Wywołaj procedurę sortującą dla drugiej części ciągu.
Dla poprawności działania powyższego algorytmu nie ma znaczenia, który element zostanie wybrany jako element rozdzielający ciąg na dwie części. Ma to jednak wpływ na efektywność algorytmu. Najczęściej wybierany jest pierwszy element ciągu (tak jest w naszym przypadku) lub element losowy. Czas działania tego algorytmu sortowania zależy od wielkości podziałów wykonywanych przez procedurę dzielącą ciąg. Jeżeli podziały te są zrównoważone, czyli wielkości powstających części są sobie równe, to algorytm ten jest praktycznie najszybszą metodą sortowania - stąd jego nazwa: sortowanie szybkie (ang. quicksort). Jeżeli natomiast otrzymane w wyniku podziału ciągi mają bardzo różne długości, to złożoność algorytmu jest większa.
Sortowanie stogowe
W tej metodzie sortowania jest wykorzystywana struktura danych zwana kopcem. Elementy tablicy tworzą kopiec, jeżeli dla każdego indeksu i zachodzi warunek :
A[i/2] >= A[i]
Tablicę można przedstawić jako drzewo binarne, w którym kolejne jej elementy są umieszczone poziomami od góry.
Dla tablicy o siedmiu elementach drzewo binarne ma następującą postać:
Drzewo binarne jest kopcem, jeśli każdy element jest większy lub równy niż elementy w drzewie leżące pod nim na poziomach niższych.
Z warunku kopca (w obu sformułowaniach) wynika m.in., że w korzeniu takiego drzewa (czyli na początku tablicy) znajduje się element maksymalny.
Bardzo ważną procedurą w algorytmie, który chcemy opisać, jest przywracanie własności kopca dla pewnego elementu A[i]. Przy wywołaniu tej procedury zakłada się, że drzewa zaczepione w lewym i prawym synu wierzchołka zawierającego element A[i] są kopcami. Po zakończeniu działania procedury, drzewo zaczepione w wierzchołku zawierającym A[i] będzie spełniać własność kopca. Działanie tej procedury jest następujące:
- Jeśli element jest mniejszy od jednego ze swych synów, to zamień go z tym synem, który ma większą wartość.
- Wywołaj procedurę rekurencyjnie dla tego z synów, który zmienił wartość.
Mając tablicę, która ma własność kopca, oraz procedurę przywracania własności kopca dla zaburzonego elementu tablicy można podać następujący algorytm porządkowania:
- Dana jest tablica A[1..n] będąca kopcem, wobec tego element A[1] jest maksymalny.
- Niech m oznacza ostatni element kopca; na początku kopiec obejmuje całą tablicę, więc m jest równe n.
- Zamień ze sobą elementy A[1] i A[m].
- Zmniejsz m o 1.
- Przywróć własność kopca dla tablicy A[1..m] zaczynając od elementu A[1].
- Wróć do kroku 3.
Pozostaje jeszcze wyjaśnić, w jaki sposób zbudować kopiec w kroku 1. Wykorzystywana jest do tego opisana wyżej procedura przywracania własności kopca, działająca na elementach tablicy w pewnej kolejności. Elementy tablicy, które są liśćmi drzewa można traktować jak jednoelementowe kopce. Procedura budująca kopiec wywołuje procedurę przywracającą własność kopca dla każdego wierzchołka, który nie jest liściem, zaczynając od elementu leżącego najbliżej końca tablicy, a kończąc na korzeniu drzewa. Przykład dla liczb - 5,7,6,1,9,2,8,4,3 :
Aby zrozumieć na czym polegają poszczególne metody sortowania polecam skorzystac z materiałow dostępnych również na innych stronach www lub pobrać program algorytmy pokazujący metody i zasady sortowania (po pobraniu należy go rozpakowac i uruchomić).
Poniżej ukazane są wizualiacje metod sortowania.
Dostęp tylko dla zalogowanych użytkowników !
|
