Sortowanie przez scalanie

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 3848 razy

Sortowanie przez scalanie to typowy przykład algorytmu rekurencyjnego, w którym konieczny jest podział danych wejściowych na podgałęzie o rozmiarze danych nie większym niż 2. Innymi słowy (tak jak pokazane zostało to na rysunku poniżej) dla przykładowych danych: 2, 6, 3, 7, 5, 4, 1, 8 wykonuje się podział na dwa podzbiory: 2, 6, 3, 7 i 5, 4, 1, 8 a następnie pierwszy zbiór znów jest dzielony na pół i po uzyskaniu zbiorów o liczebności ≤ 2 sortuje się je. Dane powracają do głównej gałęzi programu i po posortowaniu drugiej jej części są łączone z równoczesnym ich sortowaniem.

Schemat pokazujący zasadę działania algorytmu sortowania przez scalanie
Rys. 1
Schemat pokazujący zasadę działania algorytmu sortowania przez scalanie dla liczb 2, 6, 3, 7, 5, 4, 1, 8

Wadą tego algorytmu jest konieczność użycia pamięci co przy zbyt dużej liczbie podgałęzi może mieć nieprzyjemne skutki. Rozwiązaniem może być dzielenie danych na mniejsze partie i ich odpowiednie sortowania na najniższych gałęziach dowolnym znanym algorytmem sortowania. Przykładowa animacja działania algorytmu dla 50 losowo wygenerowanych wartości widoczna jest poniżej.

Rys. 2
Animacja pokazująca działanie algorytmu sortowania przez scalanie dla 50 losowych wartości:
  • czerwony - partia danych sortowanych;
  • niebieski - partia wydzielonych danych (gałąź danych);
  • zielony - pozostałe elementy tablicy

Szacunkowa złożoność czasowa tego algorytmu wynosi n · log2 n. Istnieje również wersja ulepszona pomijająca rekurencję poprzez zabranie się zna realizację algorytmu od drugiej strony w sposób iteracyjny, czyli dane wejściowe najpierw są dzielone na porcje o liczebności równej co najwyżej 2 a następnie sortowana i łączone w zbiory o liczebności nie większej niż 4 itd. z wykorzystaniem pętli.

Algorytm z powyższej animacji zapisany w JavaScript można zapisać w następujący sposób:

function mergeSort(data){ console.log("data.length: " + data.length); if(data.length > 2){ var data1 = mergeSort(data.splice(0, parseInt(data.length / 2))); var data2 = mergeSort(data); console.log("data1: " + data1.join()); console.log("data2: " + data2.join()); var sortedData = Array(); while(data1.length && data2.length){ if(data1[0] < data2[0]){ console.log("zdejmuję z data1: " + data1[0]); sortedData.push(data1.shift()); }else{ console.log("zdejmuję z data2: " + data2[0]); sortedData.push(data2.shift()); } } sortedData = sortedData.concat(data1); sortedData = sortedData.concat(data2); console.log(sortedData.join()); return sortedData; }else{ if(data.length == 2){ if(data[0] > data[1]){ console.log("przed zamianą " + data.join()); replace(data, 0, 1); console.log("po zamianie " + data.join()); } } return data; } }
Propozycje książek