Merge sort je jedním ze základních algoritmů počítačové vědy, formulovaný již v roce 1945 velkým matematikem Johnem von Neumannem. Během účasti na projektu Manhattan se Neumann potýkal s potřebou efektivně zpracovávat obrovské množství dat. Metoda, kterou vyvinul, používala princip „rozděl a panuj“, což výrazně zkrátilo čas potřebný k práci.
Princip a použití algoritmu
Metoda řazení sloučení se používá při problémech s řazením struktur, které mají objednaný přístup k prvkům, jako jsou pole, seznamy, proudy.
Během zpracování se počáteční datový blok rozdělí na malé komponenty až do jednoho prvku, který je ve skutečnosti již seřazeným seznamem. Poté se znovu sestaví ve správném pořadí.
Řazení pole určité délky vyžaduje další paměťovou oblast stejné velikosti, ve které se setříděné pole shromažďuje po částech.
Tuto metodu lze použít k objednání jakéhokoli srovnatelného datového typu, jako jsou čísla nebo řetězce.
Sloučit seřazenoplots
Abychom porozuměli algoritmu, začněme jeho analýzu od konce – od mechanismu slučování setříděných bloků.
Představme si, že máme dvě pole čísel seřazená jakýmkoli způsobem, která je třeba vzájemně kombinovat, aby se řazení neporušilo. Pro jednoduchost seřadíme čísla vzestupně.
Elementární příklad: obě pole se skládají každé z jednoho prvku.
int arr1={31}; int arr2={18};
Chcete-li je sloučit, musíte vzít nulový prvek prvního pole (nezapomeňte, že číslování začíná od nuly) a nulový prvek druhého pole. Jedná se o 31 a 18. Podle podmínek řazení by mělo být číslo 18 na prvním místě, protože je menší. Stačí seřadit čísla ve správném pořadí:
int výsledek={18, 31};
Podívejme se na složitější příklad, kde se každé pole skládá z několika prvků:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritmus sloučení bude sestávat z postupného porovnávání menších prvků a jejich umístění do výsledného pole ve správném pořadí. Abychom měli přehled o aktuálních indexech, uvedeme dvě proměnné – index1 a index2. Zpočátku je nastavíme na nulu, protože pole jsou seřazeny a nejmenší prvky jsou na začátku.
int index1=0; int index2=0;
Pojďme napsat celý proces sloučení krok za krokem:
- Vezměte prvek s indexem1 z pole arr1 a prvek s indexem2 z pole arr2.
- Porovnejte, vyberte nejmenší z nich a vložtevýsledné pole.
- Zvýšit aktuální index menšího prvku o 1.
- Pokračujte prvním krokem.
Na prvním oběhu bude situace vypadat takto:
index1=0; index2=0; arrl[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; výsledek[0]=arr1[0]; // výsledek=[2]
V druhém kole:
index1=1; index2=0; arrl[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; výsledek[1]=arr2[0]; // výsledek=[2, 5]
Třetí:
index1=1; index2=1; arrl[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; vysledek[2]=arr2[1]; // výsledek=[2, 5, 6]
A tak dále, dokud výsledkem nebude zcela seřazené pole: {2, 5, 6, 17, 21, 19, 30, 45}.
Jisté potíže mohou nastat, pokud se sloučí pole s různou délkou. Co když jeden z aktuálních indexů dosáhl posledního prvku a ve druhém poli stále zbývají členové?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 krok index1=0, index2=0; 1 2 výsledek={1, 2}; // 3 kroky index1=1, index2=1; 4 < 5 výsledek={1, 2, 4}; //4 krok index1=2, index2=1 ??
Proměnná index1 dosáhla hodnoty 2, ale pole arr1 nemá prvek s tímto indexem. Zde je vše jednoduché: stačí přenést zbývající prvky druhého pole do výsledného pole, přičemž zachová jejich pořadí.
výsledek={1, 2, 4, 5, 6, 7, 9};
Tato situace nám naznačuje potřebuporovnejte aktuální kontrolní index s délkou slučovaného pole.
Schéma sloučení pro uspořádané sekvence (A a B) různých délek:
- Pokud je délka obou sekvencí větší než 0, porovnejte A[0] a B[0] a přesuňte menší do vyrovnávací paměti.
- Pokud je délka jedné ze sekvencí 0, vezměte zbývající prvky druhé sekvence a beze změny jejich pořadí přejděte na konec vyrovnávací paměti.
Realizace druhé etapy
Příklad spojení dvou seřazených polí v Javě je uveden níže.
int a1=nový int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nový int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=nový int[a1.délka + a2.délka]; int i=0, j=0; for (int k=0; k a1.délka-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.délka-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; }
Zde:
- a1 a a2 jsou původní seřazená pole, která mají být sloučena;
- a3 – konečné pole;
- i a j jsou indexy aktuálních prvků pro pole a1 a a2.
První a druhá podmínka if zajistí, že indexy nepřekročí velikost pole. Třetí a čtvrtý blok podmínek se přesunou do výsledného pole menšího prvku.
Rozděl a panuj
Takže jsme se naučili slučovat seřazenésbírky hodnot. Dá se říci, že druhá část algoritmu řazení sloučení - samotné sloučení - již byla seřazena.
Stále však musíte pochopit, jak se dostat z původního neseřazeného pole čísel k několika seřazeným, která lze sloučit.
Podívejme se na první fázi algoritmu a naučte se, jak oddělovat pole.
To není těžké - původní seznam hodnot je rozdělen na polovinu, pak je každá část také rozdvojena a tak dále, dokud nezískáte velmi malé bloky.
Délka takových minimálních prvků může být rovna jedné, to znamená, že samy mohou být setříděným polem, ale není to nutná podmínka. Velikost bloku je určena předem a k jeho objednání lze použít jakýkoli vhodný třídicí algoritmus, který efektivně pracuje s poli malých velikostí (například rychlé třídění nebo vkládání).
Vypadá to takto.
// původní pole {34, 95, 10, 2, 102, 70}; // první rozdělení {34, 95, 10} a {2, 102, 70}; // druhý mezičas {34} a {95, 10} a {2} a {102, 70
Výsledné bloky sestávající z 1-2 prvků lze velmi snadno uspořádat.
Poté je potřeba sloučit již roztříděná malá pole do párů, se zachováním pořadí členů, což jsme se již naučili.
Realizace první fáze
Rekurzivní rozdělení pole je zobrazeno níže.
void mergeSort(T a, dlouhý začátek, dlouhý konec) { long split; -li(start < cíl) { split=(start + cíl)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); }
Co se stane v tomto kódu:
-
Funkce mergeSort získá počáteční pole
a
a levý a pravý okraj oblasti, která má být seřazena (indexy začínají a
- finish).
-
Pokud je délka této části větší než jedna (
začátek < cíl
), pak je rozdělena na dvě části (podle indexu
- split) a každý z nich je rekurzivně tříděn.
-
Při volání rekurzivní funkce pro levou stranu se předává počáteční index grafu a index
split
. U pravé části bude začátek
- (rozdělit + 1) a konec bude posledním indexem původní sekce.
-
Funkce
merge
získává dvě uspořádané sekvence (
a[start]…a[split]
a
- a[rozdělit +1]…a[finish]) a sloučí je v pořadí řazení.
Mechanika funkce sloučení je popsána výše.
Obecné schéma algoritmu
Metoda slučovacího pole řazení se skládá ze dvou velkých kroků:
- Rozdělte netříděné původní pole na malé kousky.
- Sbírejte je ve dvojicích podle pravidla třídění.
Velký a složitý úkol je rozdělen do mnoha jednoduchých, které se postupně řeší, což vede k požadovanému výsledku.
Vyhodnocení metody
Časová složitost řazení sloučení je určena výškou rozděleného stromualgoritmu a je rovna počtu prvků v poli (n) krát jeho logaritmus (log n). Takový odhad se nazývá logaritmický.
To je výhoda i nevýhoda metody. Jeho doba běhu se nemění ani v nejhorším případě, kdy je původní pole řazeno v obráceném pořadí. Při zpracování kompletně roztříděných dat však algoritmus neposkytuje časový zisk.
Je také důležité poznamenat si náklady na paměť metody řazení sloučení. Velikostí se rovnají původní kolekci. V této dodatečně přidělené oblasti se z kusů sestaví setříděné pole.
Implementace algoritmu
Řazení sloučení v Pascalu je zobrazeno níže.
Postup MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: celé číslo; f1, f2: text; b: booleovský Begincol:=0; Assign(f, jméno); reset(f); I když ne EOF(f) do begin read(f, a1); inc(col); konec; close(f); Assign(f1, '{jméno 1. pomocného souboru}'); Assign(f2, '{jméno 2. pomocného souboru}'); s:=1; While (s<kol) do begin Reset(f); rewrite(f1); přepsat(f2); For i:=1 to kol div 2 do begin Read(f, a1); Write(f1, a1, ' '); konec; If (kol div 2) mod s0 then begin tmp:=kol div 2; Zatímco tmp mod s0 do begin Read(f, a1); Write(f1, a1, ' '); inc(tmp); konec; konec; I když ne EOF(f), začněte Read(f, a2); Write(f2, a2, ' '); konec; close(f); close(f1); close(f2); přepsat(f); reset(f1); reset(f2); Read(f1, a1); Read(f2, a2); Zatímco (nikoli EOF(f1)) a (nikoli EOF(f2)) nezačínají i:=0; j:=0; b:=true; Zatímco (b) a (nikoli EOF(f1)) a (ne EOF(f2)) začínají If (a1<a2) then beginWrite(f, a1, ' '); Read(f1, a1); inc(i); End else begin Write(f, a2, ' '); Read(f2, a2); inc(j); konec; Jestliže (i=s) nebo (j=s), pak b:=false; konec; Pokud ne b, pak begin While (i<s) a (nikoli EOF(f1)) nezačínejte Write(f, a1, ' '); Read(f1, a1); inc(i); konec; Zatímco (j<s) a (nikoli EOF(f2)) začínají Write(f, a2, ' '); Read(f2, a2); inc(j); konec; konec; konec; I když ne EOF(f1), začněte tmp:=a1; Read(f1, a1); Pokud ne EOF(f1) then Write(f, tmp, ' ') else Write(f, tmp); konec; I když ne EOF(f2), začněte tmp:=a2; Read(f2, a2); Pokud ne EOF(f2) then Write(f, tmp, ' ') else Write(f, tmp); konec; close(f); close(f1); close(f2); s:=s2; konec; Vymazat(f1); Vymazat(f2); Konec;
Vizuálně operace algoritmu vypadá takto (nahoře - neuspořádaná sekvence, dole - uspořádaná).
Externí třídění dat
Velmi často je potřeba třídit některá data umístěná v externí paměti počítače. V některých případech mají působivou velikost a nelze je umístit do paměti RAM, aby se k nim usnadnil přístup. Pro takové případy se používají externí metody třídění.
Potřeba přístupu k externím médiím snižuje efektivitu zpracování.
Složitost práce spočívá v tom, že algoritmus může v jednu chvíli přistupovat pouze k jednomu prvku datového toku. A v tomto případě jeden z nejlepších výsledků ukazuje metoda merge sort, která dokáže porovnat prvky dvou souborů postupně jeden po druhém.
Čtení dat zexterní zdroj, jejich zpracování a zápis do výsledného souboru se provádí v uspořádaných blocích (sériích). Podle způsobu práce s velikostí objednaných sérií existují dva typy řazení: jednoduché a přirozené slučování.
Jednoduché sloučení
Jednoduchým sloučením je délka série pevná.
V původním neseřazeném souboru se tedy všechny série skládají z jednoho prvku. Po prvním kroku se velikost zvětší na dvě. Další – 4, 8, 16 a tak dále.
Funguje to takto:
- Zdrojový soubor (f) je rozdělen na dva pomocné - f1, f2.
- Opět se sloučí do jednoho souboru (f), ale zároveň se všechny prvky porovnávají ve dvojicích a tvoří dvojice. Velikost série v tomto kroku bude dvě.
- Krok 1 se opakuje.
- Krok 2 se opakuje, ale již objednané 2 se sloučí do seřazených 4.
- Smyčka pokračuje a zvyšuje řadu v každé iteraci, dokud není setříděn celý soubor.
Jak poznáte, že je vnější třídění s jednoduchým sloučením dokončeno?
- délka nové řady (po sloučení) není menší než celkový počet prvků;
- zbývá pouze jedna epizoda;
- Pomocný soubor f2 zůstal prázdný.
Nevýhody jednoduchého sloučení jsou: protože délka běhu je při každém sloučení pevná, zpracování částečně uspořádaných dat bude trvat stejně dlouho jako zcela náhodných dat.
Přirozená fúze
Tato metoda neomezuje délkusérie, ale vybere maximum možného.
Algoritmus řazení:
- Čtení počáteční sekvence ze souboru f. První přijatý prvek je zapsán do souboru f1.
- Pokud další záznam splňuje podmínku řazení, zapíše se tam, pokud ne, pak do druhého pomocného souboru f2.
- Tímto způsobem jsou distribuovány všechny záznamy zdrojového souboru a v f1 je vytvořena uspořádaná sekvence, která určuje aktuální velikost série.
- Soubory f1 a f2 jsou sloučeny.
- Cyklus se opakuje.
Vzhledem k nepevné velikosti série je nutné označit konec sekvence speciálním znakem. Při slučování se tedy zvyšuje počet srovnání. Kromě toho se velikost jednoho z pomocných souborů může blížit velikosti originálu.
Přirozené sloučení je v průměru efektivnější než jednoduché sloučení s externím řazením.
Funkce algoritmu
Při porovnávání dvou stejných hodnot metoda zachovává jejich původní pořadí, to znamená, že je stabilní.
Proces řazení lze velmi úspěšně rozdělit do několika vláken.
Video jasně ukazuje fungování algoritmu řazení sloučení.
