Sortowanie przez scalanie
Stronę tą wyświetlono już: 2839 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.
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.
- 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;
- }
- }
Tytuł:
Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie
Autor:
Ryan T. White, Archana Tikayat Ray
Tytuł:
Algorytmy kryptograficzne w Pythonie. Wprowadzenie
Autor:
Shannon W. Bray
Tytuł:
Algorytmy sztucznej inteligencji. Ilustrowany przewodnik
Autor:
Rishal Hurbans
Tytuł:
Algorytmy bez tajemnic
Autor:
Thomas H. Cormen
Tytuł:
Algorytmy dla bystrzaków
Autor:
John Paul Mueller, Luca Massaron
Tytuł:
Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II
Autor:
David Natingga
Tytuł:
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Autor:
Giuseppe Bonaccorso
Tytuł:
Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących
Autor:
James Cutajar
Tytuł:
C++. Struktury danych i algorytmy
Autor:
Wisnu Anggoro
Tytuł:
Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji
Autor:
Marcin Jamro