|
Strona główna
Ważne definicje:
Algorytmy sortowania:
Porównanie algorytmów
Instrukcja użytkownika
Informacja o programie
|
|
Opis algorytmu
|
W algorytmie sortowania przez scalanie jest wykorzystywana strategia "dziel i zwyciężaj". Jest to bardzo efektywna technika algorytmiczna
(wykorzystana jest także w algorytmie sortowania "szybkiego").
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.
|
Demonstracja
|
Poniższy applet demonstruje działanie opisanego algorytmu sortowania.
Dostępna jest również nieco rozbudowana demonstracja tego algorytmu, pokazująca operacje wykonywane na danych przechowywanych w pamięci dodatkowej.
Dane do sortowania mogą być losowe, uporządkowane lub odwrotnie uporządkowane.
- Zieloną i niebieską kropką są zaznaczone aktualnie porównywane elementy.
- Zieloną i pomarańczową linią są zaznaczone scalane podciągi.
- Aby uruchomić demonstrację, naciśnij Start.
- Aby zatrzymać demonstrację, naciśnij Stop.
- Aby wykonać jeden krok algorytmu, naciśnij Krok.
- Aby przyspieszyć działanie, naciśnij >.
- Aby spowolnić działanie, naciśnij <.
- Aby zmienić typ danych, użyj pola wyboru Typ danych.
- Aby zmienić wielkość danych, użyj pola edycyjnego Wielkość danych i naciśnij przycisk Zmień dane.
Wielkość danych musi być liczbą z zakresu od 5 do 300.
|
