Odporúčaná, 2024

Redakcia Choice

Rozdiel medzi triedením rýchleho triedenia a zlúčením

Rýchle algoritmy triedenia a zlúčenia sú založené na algoritme rozdelenia a dobývania, ktorý funguje podobným spôsobom. Predtým rozdiel medzi rýchlym zlúčením a zlúčením je, že pri rýchlom triedení sa otočný prvok používa na triedenie. Na druhej strane zlúčenie triedenia nepoužíva na vykonanie triedenia prvok pivot.

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 porovnanieRýchle triedenieZlúčiť triedenie
Rozdelenie prvkov do poľaRozdelenie zoznamu prvkov nie je nevyhnutne rozdelené na polovicu.Pole je vždy rozdelené na polovicu (n / 2).
Najhorší prípad zložitostiO (n2)O (n log n)
Funguje dobreMenšie poleFunguje 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ý priestormenejviac
efektívnosťNeúčinná pre väčšie polia.Viac efektívny.
Metóda triedeniainterný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.

  1. Prvý prvok alebo akýkoľvek náhodný prvok vybraný ako kľúč, predpokladajme kľúč = A (1).
  2. Ukazovateľ "nízky" je umiestnený na druhom a ukazovateľ "hore" je umiestnený na poslednom prvku poľa, tj nízky = 2 a hore = n;
  3. Postupne zvyšujte ukazovateľ "nízka" o jednu pozíciu, kým sa nezobrazí (A [low]>).
  4. Konštantne znižujte ukazovateľ "nahor" o jednu pozíciu, až kým (A [up] <= kľúč).
  5. Ak je hore väčšia ako nízka výmena A [nízka] s A [up].
  6. Opakujte kroky 3, 4 a 5, až kým stav v kroku 5 zlyhá (tj hore <= nízka), potom vymeniť A [hore] kľúčom.
  7. 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.
  8. 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.

  1. 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é.
  2. 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]).
  3. 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

  1. 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.
  2. 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).
  3. 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.
  4. Rýchle triedenie je v niektorých prípadoch rýchlejšie než zlúčenie, napríklad pri malých množinách údajov.
  5. 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.
  6. Zlúčenie je efektívnejšie ako rýchle triedenie.
  7. 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).

Top