Techniky triedenia, rýchle triedenie a zlúčenie sú založené na metóde rozdelenia a dobývania, v ktorej sú súbory prvkov rozdelené a potom spojené po preusporiadaní. Rýchle triedenie zvyčajne vyžaduje viac porovnaní než zlučovanie triedenia pre triedenie veľkého množstva prvkov.
Porovnávacia tabuľka
| Základ pre porovnanie | Rýchle triedenie | Zlúčiť triedenie |
|---|---|---|
| Rozdelenie prvkov do poľa | Rozdelenie zoznamu prvkov nie je nevyhnutne rozdelené na polovicu. | Pole je vždy rozdelené na polovicu (n / 2). |
| Najhorší prípad zložitosti | O (n2) | O (n log n) |
| Funguje dobre | Menšie pole | Funguje jemne v akomkoľvek type poľa. |
| rýchlosť | Rýchlejšie ako iné triediace algoritmy pre malý súbor údajov. | Konzistentná rýchlosť vo všetkých typoch súborov údajov. |
| Dodatočné požiadavky na úložný priestor | menej | viac |
| efektívnosť | Neúčinná pre väčšie polia. | Viac efektívny. |
| Metóda triedenia | interný | externý |
Definícia rýchleho triedenia
Rýchle triedenie je všadeprítomne používaný algoritmus triedenia, pretože je rýchly pre krátke polia. Súbor prvkov je opakovane rozdelený na časti, kým nie je možné ich ďalej rozdeliť. Rýchle triedenie je tiež známe ako triedenie rozdelenia oblastí . Používa kľúčový prvok (známy ako pivot) pre rozdelenie prvkov. Jeden oddiel obsahuje tie prvky, ktoré sú menšie ako kľúčový prvok. Iný oddiel obsahuje tie prvky, ktoré sú väčšie ako kľúčový prvok. Prvky sa triedia rekurzívne.
Predpokladajme, že A je pole A [1], A [2], A [3], ......, A [n] n čísla, ktoré je potrebné zoradiť. Algoritmus rýchleho triedenia pozostával z nasledujúcich krokov.
- Prvý prvok alebo akýkoľvek náhodný prvok vybraný ako kľúč, predpokladajme kľúč = A (1).
- Ukazovateľ "nízky" je umiestnený na druhom a ukazovateľ "hore" je umiestnený na poslednom prvku poľa, tj nízky = 2 a hore = n;
- Postupne zvyšujte ukazovateľ "nízka" o jednu pozíciu, kým sa nezobrazí (A [low]>).
- Konštantne znižujte ukazovateľ "nahor" o jednu pozíciu, až kým (A [up] <= kľúč).
- Ak je hore väčšia ako nízka výmena A [nízka] s A [up].
- Opakujte kroky 3, 4 a 5, až kým stav v kroku 5 zlyhá (tj hore <= nízka), potom vymeniť A [hore] kľúčom.
- Ak prvky, ktoré sú vľavo od kľúča, sú menšie ako kľúč a prvky vpravo od kľúča sú väčšie ako kľúč, potom pole je rozdelené na dve podradené polia.
- Vyššie uvedený postup sa opakovane aplikuje na subarrays, kým nie je triedené celé pole.
Výhody a nevýhody
Má dobré priemerné správanie. Rýchlosť triedenia dobe trvania je dobrá, pretože je rýchlejšia ako algoritmy ako triedenie bublín, triedenie vkladania a triedenie výberu. Je však zložitá a veľmi rekurzívna, preto nie je vhodná pre veľké polia.
Definícia zlúčenia
Merge sort je externý algoritmus, ktorý je tiež založený na stratégii delenia a dobývania. Prvky sú rozdelené na podradené polia (n / 2) znova a znova, kým zostane iba jeden prvok, čo výrazne skracuje čas triedenia. Používa sa na ukladanie pomocného poľa ďalšie úložisko. Zlúčiť triedenie používa tri polia, kde sa dve slúži na ukladanie každej polovice a tretia sa používa na uloženie konečného zoradeného zoznamu. Každé pole sa potom rekurzívne triedi. Nakoniec sú subarrays zlúčené, aby sa vytvorila n veľkosť prvku poľa. Zoznam je vždy rozdelený na iba polovicu (n / 2), čo sa líši od rýchleho triedenia.
Nech A je pole n počet prvkov, ktoré majú byť triedené A [1], A [2], ........., A [n]. Spôsob zlučovania nasleduje po daných krokoch.
- Rozdelte pole A do približne n / 2 triedeného podradníka o 2, čo znamená, že prvky v (A [1], A [2]), (A [3], A [ k], A [k + 1]), submenu (A [n-1], A [n]) musia byť zoradené.
- Kombinujte každú dvojicu párov, aby ste získali zoznam triedených subarrays veľkosti 4; prvky v subarrays sú tiež v triedenom poradí (A [1], A [2], A [3], A [4]), ......, A [k-1] [k + 1], A [k + 2]), ... (A [n-3], A [n-2], A [n-1], A [n]).
- Krok 2 sa opakovane vykoná až dovtedy, kým nie je iba jedno zoradené pole veľkosti n.
Výhody a nevýhody
Algoritmus zlúčenia sa vykonáva presne rovnakým a presným spôsobom bez ohľadu na počet prvkov zahrnutých do triedenia. Funguje to dokonca aj pri veľkej dátovej zostave. Avšak, spotrebuje väčšiu časť pamäte.
Kľúčové rozdiely medzi rýchlou triedou a zlučovaním
- Pri zlúčeniach zlúčenia musí byť pole rozdelené na dve polovice (tj n / 2). Na rozdiel od toho, v rýchlom triedení, neexistuje nutnosť rozdelenia zoznamu na rovnaké prvky.
- Najhoršou zložitosťou rýchleho triedenia je O (n2), pretože v najhoršom stave je oveľa viac porovnaní. Na rozdiel od toho, zlúčenie majú rovnaký najhorší prípad a priemernú komplexnosť prípadov, to znamená O (n log n).
- Zoskupenie môže fungovať dobre na akomkoľvek type dátových súborov, či je veľký alebo malý. Na druhej strane rýchle triedenie nemôže fungovať s veľkými množinami údajov.
- Rýchle triedenie je v niektorých prípadoch rýchlejšie než zlúčenie, napríklad pri malých množinách údajov.
- Typ zlučovania vyžaduje dodatočný priestor na ukladanie pomocných polí. Na druhej strane rýchle triedenie nevyžaduje veľa priestoru na ďalšie ukladanie.
- Zlúčenie je efektívnejšie ako rýchle triedenie.
- Rýchle zoradenie je metóda interného zoraďovania, pri ktorej sa údaje, ktoré sa majú zoradiť, nastavia v čase v hlavnej pamäti. Naopak, triedenie zlúčenia je externá metóda triedenia, v ktorej údaje, ktoré sa majú zoradiť, nemôžu byť súčasne uložené v pamäti a niektoré musia byť uložené v pomocnej pamäti.
záver
Rýchle zoradenie je rýchlejšie, ale v niektorých situáciách je neefektívne a tiež vykonáva veľa porovnaní v porovnaní so zlúčením. Hoci zlúčenie triedenia vyžaduje menej porovnania, potrebuje ďalší pamäťový priestor 0 (n) na uloženie extra poľa, zatiaľ čo rýchle triedenie potrebuje priestor O (log n).
