Obsah

• Porovnávacia tabuľka
• Definícia rýchleho zoradenia
• Definícia triedenia zlúčenia
• záver

Algoritmy rýchleho zoradenia a zlúčenia sú založené na algoritme rozdelenia a dobývania, ktorý funguje veľmi podobným spôsobom. Predchádzajúci rozdiel medzi rýchlym a zlúčeným triedením je ten, že pri rýchlom triedení sa na triedenie použije otočný prvok. Na druhej strane zlúčenie triedenia nepoužíva na vykonávanie triedenia otočný prvok.

Obidve techniky triedenia, rýchle zoradenie a zlúčené zoradenie sú postavené na metóde rozdelenia a dobývania, pri ktorej sa súbor prvkov rozdeľuje a po preusporiadaní kombinuje. Rýchle zoradenie zvyčajne vyžaduje viac tried ako zlúčené zoradenie na triedenie veľkého množstva prvkov.

1. 1. Porovnávacia tabuľka
   2. definícia
   3. Kľúčové rozdiely
   4. záver

Porovnávacia tabuľka

Základ pre porovnanie	Rýchle zoradenie	Zlúčiť zoradenie
Rozdelenie prvkov v poli	Rozdelenie zoznamu prvkov sa nemusí nevyhnutne rozdeliť na polovicu.	Pole je vždy rozdelené na polovicu (n / 2).
Najhoršia zložitosť	O (n2)	O (n log n)
Funguje dobre	Menšie pole	Funguje dobre v akomkoľvek type poľa.
rýchlosť	Rýchlejšie ako iné triediace algoritmy pre malú množinu údajov.	Rovnaká rýchlosť vo všetkých typoch súborov údajov.
Požiadavka na ďalší úložný priestor	menej	viac
efektívnosť	Neefektívne pre väčšie polia.	Viac efektívny.
Metóda triedenia	interný	externý

Definícia rýchleho zoradenia

Rýchle zoradenie je všade používaný algoritmus triedenia, pretože je rýchly pre krátke polia. Súbor prvkov sa opakovane delí na časti, až kým nie je možné ho ďalej deliť. Rýchle zoradenie je tiež známe ako radenie podľa oblasti, Na rozdelenie prvkov používa kľúčový prvok (známy ako pivot). 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 sú rekurzívne usporiadané.

Predpokladajme, že A je pole A, A, A, …… .., A s číslom n, ktoré je potrebné triediť. Algoritmus rýchleho zoradenia pozostával z nasledujúcich krokov.

1. Prvý prvok alebo ľubovoľný náhodný prvok vybraný ako kľúč predpokladá kľúč = A (1).
2. Ukazovateľ „nízka“ je umiestnená na druhom a ukazovateľ „hore“ je umiestnený na poslednom prvku poľa, t. J. Nízka = 2 a vyššia = n;
3. Dôsledne zvyšujte ukazovateľ „low“ o jednu pozíciu, kým (klávesa A>).
4. Neustále znižujte ukazovateľ „hore“ o jednu pozíciu, kým (A <= klávesa).
5. Ak je hore vyššia ako nízka, prepnite A s A.
6. Opakujte kroky 3,4 a 5, až kým stav v kroku 5 zlyhá (t.j. hore <= nízka), potom zameňte A za kľúč.
7. Ak sú prvky vľavo od kľúča menšie ako kľúč a prvky vpravo od kľúča sú väčšie ako kľúč, potom sa pole rozdelí do dvoch čiastkových polí.
8. Vyššie uvedený postup sa opakovane aplikuje na čiastkové polia, až kým nebude zoradené celé pole.

   

   
   

Výhody a nevýhody

Má dobré priemerné správanie. Zložitosť prevádzkového času rýchleho zoradenia je dobrá, je rýchlejšia ako algoritmy, ako napríklad triedenie bubliniek, vkladanie a výber. Je však zložitý a veľmi rekurzívny, preto nie je vhodný pre veľké polia.

Definícia triedenia zlúčenia

Zlúčiť zoradenie je externý algoritmus, ktorý je tiež založený na stratégii rozdelenia a dobývania. Prvky sa rozdelia na čiastkové polia (n / 2) znova a znova, až kým nezostane iba jeden prvok, čo významne skracuje čas triedenia. Na ukladanie pomocného poľa používa ďalšie úložisko. Zlúčiť triedenie používa tri polia, z ktorých dve sa používajú na ukladanie každej polovice a tretí sa používa na ukladanie konečného zoradeného zoznamu. Každé pole sa potom rekurzívne triedi. Nakoniec sa podjednotky zlúčia, aby z nich urobila n veľkosť prvku poľa. Zoznam bol vždy rozdelený na polovicu (n / 2) odlišnú od rýchleho zoradenia.

Nech A je pole n počtu prvkov, ktoré sa majú triediť A, A, ………, A. Triedenie zlúčenia nasleduje dané kroky.

1. Rozdeľte maticu A na približne n / 2 zoradené podskupinu po 2, čo znamená, že prvky v podskupinách (A, A), (A, A), (A, A), (A, A) musia byť zoradené.
2. Skombinujte každú dvojicu, aby ste získali zoznam triedených podskupín veľkosti 4; prvky v čiastkových poliach sú tiež zoradené v poradí (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Krok 2 sa opakovane uskutočňuje, až kým nebude k dispozícii iba jedno zoradené pole veľkosti n.

   

Výhody a nevýhody

Algoritmus zlúčenia zoradenia funguje presne a presne bez ohľadu na počet prvkov zahrnutých v triedení. Funguje dobre aj pri veľkých množinách údajov. Spotrebúva však väčšiu časť pamäte.

1. Pri zlúčenom usporiadaní sa musí pole rozdeliť na dve polovice (t. J. 2). Naopak, v rýchlom usporiadaní nie je nútené rozdeliť zoznam na rovnaké prvky.
2. Najhoršia zložitosť rýchleho zoradenia je O (n²), pretože to vyžaduje oveľa viac porovnaní v najhoršom stave. Naproti tomu zlúčené zoradenie má rovnaké najhoršie a priemerné zložité prípady, to znamená O (n log n).
3. Zlúčiť triedenie môže fungovať dobre na akomkoľvek type množiny údajov, či už je veľký alebo malý. Naopak, rýchle zoradenie nemôže dobre fungovať s veľkými množinami údajov.
4. Rýchle zoradenie je v niektorých prípadoch rýchlejšie ako zlúčenie, napríklad pre malé súbory údajov.
5. Zlúčiť zoradenie vyžaduje ďalšie pamäťové miesto na uloženie pomocných polí. Na druhej strane, rýchle zoradenie nevyžaduje viac miesta na ďalšie úložisko.
6. Zlúčiť zoradenie je efektívnejšie ako rýchle zoradenie.
7. Rýchle zoradenie je metóda interného triedenia, pri ktorej sa údaje, ktoré sa majú triediť, upravujú naraz v hlavnej pamäti. Naopak, zlúčené triedenie je spôsob externého triedenia, pri ktorom údaje, ktoré sa majú triediť, nemôžu byť uložené v pamäti súčasne a niektoré sa musia uchovávať v pomocnej pamäti.

záver

Rýchle zoradenie je rýchlejším prípadom, ale v niektorých situáciách je neefektívne a v porovnaní s zlúčeným zoradením tiež vykoná veľa porovnaní. Aj keď zlúčené zoradenie vyžaduje menšie porovnanie, na uloženie ďalšieho poľa je potrebné ďalšie pamäťové miesto 0 (n), zatiaľ čo rýchle zoradenie vyžaduje priestor O (log n).