Sortowanie przez scalanie

Stronę tą wyświetlono już: 100 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();
  9. while(data1.length && data2.length){
  10. if(data1[0] < data2[0]){
  11. console.log("zdejmuję z data1: " + data1[0]);
  12. sortedData.push(data1.shift());
  13. }else{
  14. console.log("zdejmuję z data2: " + data2[0]);
  15. sortedData.push(data2.shift());
  16. }
  17. }
  18. sortedData = sortedData.concat(data1);
  19. sortedData = sortedData.concat(data2);
  20. console.log(sortedData.join());
  21. return sortedData;
  22. }else{
  23. if(data.length == 2){
  24. if(data[0] > data[1]){
  25. console.log("przed zamianą " + data.join());
  26. replace(data, 0, 1);
  27. console.log("po zamianie " + data.join());
  28. }
  29. }
  30. return data;
  31. }
  32. }

Komentarze