Merge sort je jedným zo základných algoritmov počítačovej vedy, ktorý v roku 1945 sformuloval veľký matematik John von Neumann. Počas účasti na projekte Manhattan čelil Neumann potrebe efektívne spracovať obrovské množstvo údajov. Metóda, ktorú vyvinul, využívala princíp „rozdeľuj a panuj“, čo výrazne skrátilo čas potrebný na prácu.
Princíp a použitie algoritmu
Metóda hromadného triedenia sa používa pri problémoch s triediacimi štruktúrami, ktoré majú objednaný prístup k prvkom, ako sú polia, zoznamy, prúdy.
Počas spracovania sa počiatočný dátový blok rozdelí na malé komponenty až po jeden prvok, ktorý je v skutočnosti už zoradeným zoznamom. Potom sa znova zloží v správnom poradí.
Zoraďovanie poľa určitej dĺžky vyžaduje dodatočnú pamäťovú oblasť rovnakej veľkosti, v ktorej sa zoradené pole zhromažďuje po častiach.
Túto metódu možno použiť na objednanie akéhokoľvek porovnateľného typu údajov, ako sú čísla alebo reťazce.
Zlúčiť zoradenéparcely
Aby sme pochopili algoritmus, začnime jeho analýzu od konca – od mechanizmu spájania triedených blokov.
Predstavme si, že máme dve polia čísel zoradených ľubovoľným spôsobom, ktoré je potrebné navzájom skombinovať, aby sa triedenie neporušilo. Pre jednoduchosť zoradíme čísla vzostupne.
Elementárny príklad: obe polia pozostávajú z každého z jedného prvku.
int arr1={31}; int arr2={18};
Ak ich chcete zlúčiť, musíte vziať nulový prvok prvého poľa (nezabudnite, že číslovanie začína od nuly) a nulový prvok druhého poľa. Ide o 31 a 18. Podľa podmienok zoradenia by malo byť číslo 18 na prvom mieste, keďže je menej. Stačí dať čísla v správnom poradí:
int výsledok={18, 31};
Pozrime sa na komplikovanejší príklad, kde každé pole pozostáva z niekoľkých prvkov:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritmus zlúčenia bude pozostávať z postupného porovnávania menších prvkov a ich umiestňovania do výsledného poľa v správnom poradí. Aby sme mali prehľad o aktuálnych indexoch, predstavme si dve premenné – index1 a index2. Spočiatku ich nastavíme na nulu, pretože polia sú zoradené a najmenšie prvky sú na začiatku.
int index1=0; int index2=0;
Napíšme si celý proces zlučovania krok za krokom:
- Zoberte prvok s indexom1 z poľa arr1 a prvok s indexom2 z poľa arr2.
- Porovnajte, vyberte najmenšiu z nich a vložtevýsledné pole.
- Zvýšte aktuálny index menšieho prvku o 1.
- Pokračujte prvým krokom.
Na prvom oblete bude situácia vyzerať takto:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; vysledok[0]=arr1[0]; // výsledok=[2]
Na druhom kole:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; vysledok[1]=arr2[0]; // výsledok=[2, 5]
Tretí:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; vysledok[2]=arr2[1]; // výsledok=[2, 5, 6]
A tak ďalej, kým výsledkom nebude úplne zoradené pole: {2, 5, 6, 17, 21, 19, 30, 45}.
Ak sa zlúčia polia s rôznymi dĺžkami, môžu nastať určité ťažkosti. Čo ak jeden z aktuálnych indexov dosiahol posledný prvok a v druhom poli stále zostávajú členovia?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 krok index1=0, index2=0; 1 2 výsledok={1, 2}; // index 3 krokov1=1, index2=1; 4 < 5 výsledok={1, 2, 4}; //4 krok index1=2, index2=1 ??
Premenná index1 dosiahla hodnotu 2, ale pole arr1 neobsahuje prvok s týmto indexom. Všetko je tu jednoduché: stačí preniesť zostávajúce prvky druhého poľa do výsledného poľa, pričom sa zachová ich poradie.
výsledok={1, 2, 4, 5, 6, 7, 9};
Táto situácia nám naznačuje potrebuporovnajte aktuálny kontrolný index s dĺžkou zlučovaného poľa.
Schéma zlúčenia pre usporiadané sekvencie (A a B) rôznych dĺžok:
- Ak je dĺžka oboch sekvencií väčšia ako 0, porovnajte A[0] a B[0] a presuňte menšiu do vyrovnávacej pamäte.
- Ak je dĺžka jednej zo sekvencií 0, vezmite zostávajúce prvky druhej sekvencie a bez zmeny ich poradia prejdite na koniec vyrovnávacej pamäte.
Implementácia druhej etapy
Príklad spojenia dvoch triedených polí v jazyku Java je uvedený nižšie.
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ĺžka + a2.dĺžka]; int i=0, j=0; for (int k=0; k a1.dĺžka-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.dĺžka-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++; }
Tu:
- a1 a a2 sú pôvodné zoradené polia, ktoré sa majú zlúčiť;
- a3 – konečné pole;
- i a j sú indexy aktuálnych prvkov pre polia a1 a a2.
Prvá a druhá ak podmienky zabezpečujú, že indexy nepresiahnu veľkosť poľa. Tretí a štvrtý blok podmienok sa presunú do výsledného poľa menšieho prvku.
Rozdeľ a panuj
Takže sme sa naučili spájať zoradenézbierky hodnôt. Dá sa povedať, že druhá časť triediaceho algoritmu zlučovania – samotné zlučovanie – už bola zoradená.
Stále však musíte pochopiť, ako sa dostať z pôvodného nezoradeného poľa čísel na niekoľko zoradených čísel, ktoré možno zlúčiť.
Pozrime sa na prvú fázu algoritmu a naučte sa, ako oddeliť polia.
Nie je to ťažké – pôvodný zoznam hodnôt je rozdelený na polovicu, potom je každá časť tiež rozdvojená a tak ďalej, až kým nezískate veľmi malé bloky.
Dĺžka takýchto minimálnych prvkov sa môže rovnať jednej, to znamená, že samy môžu byť triedeným poľom, nie je to však nevyhnutná podmienka. Veľkosť bloku je určená vopred a na jeho objednanie je možné použiť akýkoľvek vhodný triediaci algoritmus, ktorý efektívne pracuje s poliami malých veľkostí (napríklad rýchle triedenie alebo vkladanie triedenia).
Vyzerá to takto.
// pôvodné pole {34, 95, 10, 2, 102, 70}; // prvé rozdelenie {34, 95, 10} a {2, 102, 70}; // druhá časť {34} a {95, 10} a {2} a {102, 70
Výsledné bloky pozostávajúce z 1-2 prvkov sa dajú veľmi ľahko usporiadať.
Potom musíte zlúčiť už zoradené malé polia do párov, pričom zachováte poradie členov, čo sme sa už naučili robiť.
Implementácia prvej etapy
Rekurzívne rozdelenie poľa je zobrazené nižšie.
void mergeSort(T a, dlhý začiatok, dlhý koniec) { long split; ak(štart < cieľ) { split=(štart + cieľ)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); zlúčiť (a, začať, rozdeliť, skončiť); }
Čo sa stane v tomto kóde:
-
Funkcia mergeSort získa počiatočné pole
a
a ľavý a pravý okraj oblasti, ktorá sa má zoradiť (indexy začínajú a
- finish).
-
Ak je dĺžka tejto časti väčšia ako jedna (
začiatok < cieľ
), potom je rozdelená na dve časti (podľa indexu
- split) a každý z nich je rekurzívne triedený.
-
Pri volaní rekurzívnej funkcie pre ľavú stranu sa odovzdáva počiatočný index grafu a index
split
. Pre pravú časť bude začiatok
- (rozdeliť + 1) a koniec bude posledný index pôvodnej sekcie.
-
Funkcia
merge
získa dve usporiadané sekvencie (
a[začiatok]…a[rozdeliť]
a
- a[rozdeliť +1]…a[finish]) a zlúči ich v poradí zoradenia.
Mechanika funkcie zlúčenia je popísaná vyššie.
Všeobecná schéma algoritmu
Metóda zlučovacieho triediaceho poľa pozostáva z dvoch veľkých krokov:
- Rozdeľte netriedené pôvodné pole na malé kúsky.
- Pozbierajte ich do párov podľa pravidla triedenia.
Veľká a zložitá úloha je rozdelená do mnohých jednoduchých úloh, ktoré sa postupne riešia a vedú k požadovanému výsledku.
Vyhodnotenie metódy
Časová náročnosť triedenia zlúčenia je určená výškou rozdeleného stromualgoritmu a rovná sa počtu prvkov v poli (n) krát jeho logaritmus (log n). Takýto odhad sa nazýva logaritmický.
Toto je výhoda aj nevýhoda metódy. Jeho doba chodu sa nemení ani v najhoršom prípade, keď je pôvodné pole zoradené v opačnom poradí. Pri spracovaní úplne zoradených údajov však algoritmus neposkytuje časový zisk.
Je tiež dôležité si všimnúť náklady na pamäť metódy triedenia zlúčením. Veľkosťou sa rovnajú pôvodnej kolekcii. V tejto dodatočne pridelenej oblasti je z kusov zostavené triedené pole.
Implementácia algoritmu
Zlúčenie v Pascale je zobrazené nižšie.
Postup MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: celé číslo; f1, f2: text; b: boolovská hodnota Begincol:=0; Assign(f, name); reset(f); Aj keď nie EOF(f), začnite čítať (f, a1); inc(col); koniec; close(f); Assign(f1, '{názov 1. pomocného súboru}'); Assign(f2, '{názov 2. pomocného súboru}'); s:=1; Kým (s<kol) začne Reset(f); prepis(f1); prepis(f2); For i:=1 to kol div 2 do begin Read(f, a1); Write(f1, a1, ' '); koniec; If (kol div 2) mod s0 then begin tmp:=kol div 2; Kým tmp mod s0 začne Čítať (f, a1); Write(f1, a1, ' '); inc(tmp); koniec; koniec; Aj keď nie EOF(f), nezačnite Čítať (f, a2); Write(f2, a2, ' '); koniec; close(f); close(f1); close(f2); prepis(f); reset(f1); reset(f2); Read(f1, a1); Read(f2, a2); Zatiaľ čo (nie EOF(f1)) a (nie EOF(f2)) začínajú i:=0; j:=0; b:=pravda; Kým (b) a (nie EOF(f1)) a (nie EOF(f2)) začínajú If (a1<a2) then beginWrite(f, a1, ' '); Read(f1, a1); inc(i); End else begin Zapis(f, a2, ' '); Read(f2, a2); inc(j); koniec; Ak (i=s) alebo (j=s), potom b:=false; koniec; Ak nie b, potom begin While (i<s) a (nie EOF(f1)) nezačnite Write(f, a1, ' '); Read(f1, a1); inc(i); koniec; Kým (j<s) a (nie EOF(f2)) začínajú Write(f, a2, ' '); Read(f2, a2); inc(j); koniec; koniec; koniec; Aj keď nie EOF(f1), nezačnite tmp:=a1; Read(f1, a1); Ak nie EOF(f1), potom Write(f, tmp, ' ') else Write(f, tmp); koniec; Aj keď nie EOF(f2), nezačnite tmp:=a2; Read(f2, a2); Ak nie EOF(f2), potom Write(f, tmp, ' ') else Write(f, tmp); koniec; close(f); close(f1); close(f2); s:=s2; koniec; Erase(f1); Erase(f2); Koniec;
Vizuálne vyzerá činnosť algoritmu takto (hore - neusporiadaná sekvencia, dole - usporiadané).
Externé triedenie údajov
Veľmi často vzniká potreba triediť niektoré údaje umiestnené vo vonkajšej pamäti počítača. V niektorých prípadoch majú pôsobivú veľkosť a nemožno ich umiestniť do pamäte RAM, aby sa uľahčil prístup k nim. V takýchto prípadoch sa používajú externé metódy triedenia.
Potreba prístupu k externým médiám znižuje efektivitu času spracovania.
Zložitosť práce spočíva v tom, že algoritmus môže naraz pristupovať iba k jednému prvku dátového toku. A v tomto prípade jeden z najlepších výsledkov ukazuje metóda merge sort, ktorá dokáže porovnať prvky dvoch súborov postupne jeden po druhom.
Čítanie údajov zexterného zdroja, ich spracovanie a zápis do výsledného súboru prebieha v zoradených blokoch (sériách). Podľa spôsobu práce s veľkosťou objednaných sérií existujú dva typy triedenia: jednoduché a prirodzené spájanie.
Jednoduché zlúčenie
Jednoduchým zlúčením je dĺžka série pevná.
V pôvodnom netriedenom súbore teda všetky série pozostávajú z jedného prvku. Po prvom kroku sa veľkosť zväčší na dve. Ďalej – 4, 8, 16 a tak ďalej.
Funguje to takto:
- Zdrojový súbor (f) je rozdelený na dva pomocné - f1, f2.
- Opäť sa zlúčia do jedného súboru (f), no zároveň sa všetky prvky porovnávajú v pároch a tvoria dvojice. Veľkosť série sa v tomto kroku zmení na dve.
- 1. krok sa opakuje.
- Krok 2 sa opakuje, ale už zoradené 2 sa zlúčia do zoradených 4.
- Slučka pokračuje a zvyšuje sériu pri každej iterácii, až kým nie je zoradený celý súbor.
Ako viete, že vonkajšie triedenie jednoduchým zlúčením je dokončené?
- dĺžka novej série (po zlúčení) nie menšia ako celkový počet prvkov;
- zostáva len jedna epizóda;
- Pomocný súbor f2 zostal prázdny.
Nevýhody jednoduchého zlúčenia sú: keďže dĺžka spustenia je pevne stanovená pri každom prechode zlúčenia, spracovanie čiastočne usporiadaných údajov bude trvať rovnako dlho ako spracovanie úplne náhodných údajov.
Prírodné splynutie
Táto metóda neobmedzuje dĺžkuséria, ale vyberie maximum možného.
Algoritmus triedenia:
- Prečítanie počiatočnej sekvencie zo súboru f. Prvý prijatý prvok sa zapíše do súboru f1.
- Ak nasledujúci záznam spĺňa podmienku triedenia, zapíše sa tam, ak nie, zapíše sa do druhého pomocného súboru f2.
- Týmto spôsobom sa distribuujú všetky záznamy zdrojového súboru a v f1 sa vytvorí usporiadaná sekvencia, ktorá určuje aktuálnu veľkosť série.
- Súbory f1 a f2 sú zlúčené.
- Cyklus sa opakuje.
Vzhľadom na nepevnú veľkosť série je potrebné označiť koniec sekvencie špeciálnym znakom. Preto pri zlučovaní narastá počet porovnaní. Okrem toho môže byť veľkosť jedného z pomocných súborov blízka veľkosti originálu.
Prirodzené zlúčenie je v priemere efektívnejšie ako jednoduché zlúčenie s externým triedením.
Funkcie algoritmu
Pri porovnávaní dvoch rovnakých hodnôt metóda zachováva ich pôvodné poradie, to znamená, že je stabilné.
Proces triedenia sa dá veľmi úspešne rozdeliť do viacerých vlákien.
Video jasne ukazuje fungovanie algoritmu zoradenia zlúčenia.
