|
Strona główna
Ważniejsze 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, w którym się znajdował.
- 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,
przedstawione scalanie ciągów 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 (scal) 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 (scal) dwa uporządkowane ciągi w jeden ciąg uporządkowany.
|
Demonstracja
|
Poniższy aplet demonstruje nieco dokładniej proces sortowania przez scalanie. Podstawowa demonstracja tego
algorytmu została rozrzerzona o operacje wykonywane na danych przechowywanych w pamięci pomocniczej.
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 przycisk Start.
- Aby zatrzymać demonstrację, naciśnij przycisk Stop.
- Aby wykonać jeden krok algorytmu, naciśnij przycisk Krok.
- Aby przyspieszyć demonstrację, naciśnij przycisk >.
- Aby spowolnić demonstrację, naciśnij przycisk <.
- 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ń.
Wielkość danych musi być liczbą z zakresu od 5 do 300.
|
