Rýchle triedenie je interný algoritmus, ktorý je založený na stratégii rozdeľuj a panuj. V tomto:

čo je automaticky zapojené v jave

• Pole prvkov sa opakovane delí na časti, až kým nie je možné ďalej deliť.
• Je tiež známy ako triedenie výmeny priečok .
• Používa kľúčový prvok (pivot) na rozdelenie prvkov.
• Jedna ľavá oblasť obsahuje všetky prvky, ktoré sú menšie ako pivot a jedna pravá oblasť obsahuje všetky prvky, ktoré sú väčšie ako kľúčový prvok.

Zlúčiť triedenie je externý algoritmus založený na stratégii rozdeľuj a panuj. V tomto:

• Prvky sa znova a znova rozdeľujú do dvoch podpolí (n/2), kým nezostane iba jeden prvok.
• Zlúčiť triedenie používa dodatočné úložisko na triedenie pomocného poľa.
• Zoradenie zlúčením používa tri polia, z ktorých dve sa používajú na uloženie každej polovice a tretie externé sa používa na uloženie konečného zoradeného zoznamu zlúčením ďalších dvoch a každé pole sa potom triedi rekurzívne.
• Nakoniec sa všetky čiastkové polia zlúčia, aby sa dosiahla veľkosť „n“ prvkov poľa.

Rýchle zoradenie vs zlúčenie zoradenia

Rozdelenie prvkov v poli : Pri zlučovacom radení je pole rozdelené len na 2 polovice (t. j. n/2). pričom v prípade rýchleho triedenia je pole rozdelené do ľubovoľného pomeru. Nie je nútené rýchlo triediť pole prvkov na rovnaké časti. Zložitosť najhoršieho prípadu: Najhorší prípad zložitosti rýchleho triedenia je O(n^2), pretože v najhoršom stave je potrebných veľa porovnaní. zatiaľ čo pri triedení zlučovania má najhorší prípad a priemerný prípad rovnakú zložitosť O(n log n). Použitie s množinami údajov: Zoradenie zlúčením môže dobre fungovať na akomkoľvek type množín údajov bez ohľadu na ich veľkosť (veľké alebo malé). keďže rýchle triedenie nemôže dobre fungovať s veľkými množinami údajov. Požiadavka na dodatočný úložný priestor: Zoradenie zlúčením nie je zavedené, pretože vyžaduje dodatočný pamäťový priestor na uloženie pomocných polí. keďže rýchle triedenie je na mieste, pretože nevyžaduje žiadne ďalšie úložisko. Efektivita: Zlúčiť triedenie je efektívnejšie a funguje rýchlejšie ako rýchle triedenie v prípade väčšej veľkosti poľa alebo množín údajov. zatiaľ čo rýchle triedenie je efektívnejšie a funguje rýchlejšie ako zlučovacie triedenie v prípade menšej veľkosti poľa alebo množín údajov. Metóda triedenia: Rýchle triedenie je interná metóda triedenia, pri ktorej sa údaje triedia v hlavnej pamäti. pričom zlučovacie triedenie je metóda externého triedenia, pri ktorej sa dáta, ktoré sa majú triediť, nedajú umiestniť do pamäte a na triedenie je potrebná pomocná pamäť. Stabilita: Zoradenie zlúčením je stabilné, pretože dva prvky s rovnakou hodnotou sa objavia v rovnakom poradí v zoradenom výstupe, ako boli vo vstupnom nezoradenom poli. zatiaľ čo rýchle triedenie je v tomto scenári nestabilné. Ale môže byť stabilný pomocou niektorých zmien v kóde. Preferované pre : Pre polia je preferované rýchle zoradenie. zatiaľ čo triedenie Zlúčiť sa uprednostňuje pre prepojené zoznamy. Referenčná lokalita: Quicksort vykazuje dobrú vyrovnávaciu pamäť, vďaka čomu je rýchle triedenie rýchlejšie ako zlučovacie triedenie (v mnohých prípadoch ako v prostredí virtuálnej pamäte).