Obraz-algorytm

Sortowanie przez scalanie


Strona główna

Ważne definicje: Algorytmy sortowania:

Porównanie algorytmów

Instrukcja użytkownika

Informacja o programie

Do góry Do tyłu

obraz-opis

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.

obraz-działanie

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.

Sortowanie przez scalanie

Typ danych:   Wielkość danych:  

Strona główna Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez binarne wstawianie Sortowanie przez wybór Sortowanie przez scalanie Sortowanie przez scalanie - rozszerzone Sortowanie szybkie Sortowanie stogowe Sortowanie stogowe rozszerzone Porównanie algorytmów