Sortowanie przez scalanie

Stronę tą wyświetlono już: 1180 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:

Listing 1
  1. function mergeSort(data){
  2. console.log("data.length: " + data.length);
  3. if(data.length > 2){
  4. var data1 = mergeSort(data.splice(0, parseInt(data.length / 2)));
  5. var data2 = mergeSort(data);
  6. console.log("data1: " + data1.join());
  7. console.log("data2: " + data2.join());
  8. var sortedData = Array();
  10. while(data1.length && data2.length){
  11. if(data1[0] < data2[0]){
  12. console.log("zdejmuję z data1: " + data1[0]);
  13. sortedData.push(data1.shift());
  14. }else{
  15. console.log("zdejmuję z data2: " + data2[0]);
  16. sortedData.push(data2.shift());
  17. }
  18. }
  20. sortedData = sortedData.concat(data1);
  22. sortedData = sortedData.concat(data2);
  24. console.log(sortedData.join());
  26. return sortedData;
  27. }else{
  28. if(data.length == 2){
  29. if(data[0] > data[1]){
  30. console.log("przed zamianą " + data.join());
  31. replace(data, 0, 1);
  32. console.log("po zamianie " + data.join());
  33. }
  34. }
  35. return data;
  36. }
  37. }
Tematy powiązane

Komentarze