More actions
Bez shrnutí editace |
Bez shrnutí editace |
||
Riadok 1: | Riadok 1: | ||
Triediace algoritmy [[Triediace algoritmy a ich výpočtová zložitosť#Bubble-sort|Bubble-sort]], [[Triediace algoritmy a ich výpočtová zložitosť#Selection-sort|Selection-sort]], Insertion-sort, Quick-sort | Triediace algoritmy [[Triediace algoritmy a ich výpočtová zložitosť#Bubble-sort|Bubble-sort]], [[Triediace algoritmy a ich výpočtová zložitosť#Selection-sort|Selection-sort]], [[Triediace algoritmy a ich výpočtová zložitosť#Insertion-sort|Insertion-sort]], [[Triediace algoritmy a ich výpočtová zložitosť#Quick-sort|Quick-sort]], Radix-sort, Merge-sort, Heap-sort, Counting-sort, pojem výpočtovej zložitosti problému. | ||
{{Pojmová mapa}} | {{Pojmová mapa}} | ||
Riadok 39: | Riadok 39: | ||
=== Insertion-sort === | === Insertion-sort === | ||
Insertion-sort (''triedenie priamym vkladaním'') používa jednu časť triedeného poľa pre ukladanie už vytriedených hodnôt a druhú časť toho istého poľa pre hodnoty ktoré ešte nemajú správne poradie. Princíp je podobný ako pri [[Triediace algoritmy a ich výpočtová zložitosť#Selection-sort|selection-sorte]] | Insertion-sort (''triedenie priamym vkladaním'') používa jednu časť triedeného poľa pre ukladanie už vytriedených hodnôt a druhú časť toho istého poľa pre hodnoty ktoré ešte nemajú správne poradie. Princíp je podobný ako pri [[Triediace algoritmy a ich výpočtová zložitosť#Selection-sort|selection-sorte]]. | ||
. | Časová výpočtová zložitosť je <math>O(n^2)</math>. Avšak narozdiel od [[Triediace algoritmy a ich výpočtová zložitosť#Selection-sort|selection-sortu]], rýchlosť insertion-sortu závisí od vstupného poľa – pre takmer utriedené pole prebehne veľmi rýchlo. | ||
=== Quick-sort === | |||
{{Téma|Oblast=Kategória:Algoritmy a výpočtová zložitosť|Poradie=60}} | |||
[[Kategória:Algoritmy a výpočtová zložitosť]] | [[Kategória:Algoritmy a výpočtová zložitosť]] |
Verzia z 14:14, 18. apríl 2025
Triediace algoritmy Bubble-sort, Selection-sort, Insertion-sort, Quick-sort, Radix-sort, Merge-sort, Heap-sort, Counting-sort, pojem výpočtovej zložitosti problému.
Triediace algoritmy
Častým problémom v algoritmizácií je efektívne (rýchle a pamäťovo nenáročné) triedenie množiny údajov, hľadanie najväčšieho a najmenšieho čísla (respektíve, maximálnej a minimálnej hodnoty), hľadanie mediánu (prostrednej hodnoty) a modusu (hodnoty s najčastejším výskytom) a podobne.
Majme napríklad množinu čísiel: . Ako naprogramovať algoritmus ktorý takúto množinu usporiada od najmenšieho čísla po najväčšie? Touto otázkou sa zaoberali už tvorcovia algoritmov pred nami, a v súčasnosti existuje hneď niekoľko algoritmov. Každý algoritmus má svoju výpočtovú zložitosť – niektoré sú efektívnejšie pri menšom počte vstupných hodnôt, iné sú zamerané pre triedenie veľkého množstva hodnôt. Neexistuje teda definitívna odpoveď pre to, ktorý algoritmus je najlepší (ale samozrejme vo všeobecnosti vždy hľadáme algoritmus s najmenšou zložitosťou, či už časovou alebo pamäťovou).
V príklade vyššie sú uvedené čísla, ale samozrejme triedenie môžeme realizovať nad všetkým čo má pre nás nejakú postupnosť (napríklad: abecedný zoznam, zoradiť veľkosti objektov od najväčšieho po najmenší, spektrum farieb, triedenie dátumov a podobne). Neexistuje algoritmus ktorý dokáže realizovať triedenie súčasne na všetkých možných množinách prvkov (napríklad, usporiadanie písmen na klávesnici je iné ako abecedná postupnosť tých istých písmen), preto tieto algoritmy väčšinou prispôsobujeme našim potrebám. No pre jednoduchosť budeme v našich algoritmoch triediť iba postupnosti čísiel.
Bubble-sort
Za asi najznámejší triediaci algoritmus sa považuje Bubble-sort ("bublinové triedenie"). Z implementačného hľadiska je to vcelku jednoduchý algoritmus, ktorého princíp spočíva v postupnej výmene prvkov s nesprávnym poradím, pričom každý prvok "vybublá" na správne miesto.
V príklade vyššie je na vstupe pole s 5 číslami. Algoritmus bubble sort obsahuje dva vnorené cykly:
- Vonkajší cyklus zabezpečuje prechod od posledného indexu poľa k prvému. Je to preto, že s každou iteráciou v tomto cykle je garantované, že sa usporiada práve jedno číslo ("vybublá", preto sa tento algoritmus nazýva bubble-sort). Je zbytočné kontrolovať čísla, ktoré už boli správne vytriedené – preto tento cyklus začína od konca a
i
sa s každou iteráciou znižuje. - Vonkajší cyklus je ten, ktorý realizuje triedenie (porovnávanie dvoch susedných prvkov). Ak je prvý prvok väčší ako prvok ktorý nasleduje, tak sa vymenia. S každou iteráciou sa najväčšie prvky budú posúvať doprava, takže pole bude zoradené od najmenšieho po najväčší (vzostupne). Ak je potrebné čísla zoradiť naopak (od najväčšieho po najmenší, teda zostupne), tak stačí obrátiť znak porovnania (zmeniť podmienku na
if pole[j] < pole[j + 1]
).
Je to v podstate algoritmus, ktorý posúva maximálne prvky doprava (alebo doľava, ak triedime zostupne), čím sa prvky zotriedia ("vybublajú") na správne miesto.
Algoritmus bubble-sort má časovú výpočtovú zložitosť (v najhoršom prípade), je to jeden z najmenej efektívnych algoritmov. Používame ho napríklad vtedy, keď:
- Triedime menší počet hodnôt a teda takáto výpočtová zložitosť je pre nás akceptovateľná;
- Nevieme naprogramovať niečo lepšie;
Na nasledujúcej úlohe si môžeme skúsiť bubble-sort naprogramovať v Pythone:
Selection-sort
Selection-sort (triedenie výberom) algoritmus vyberá z poľa prvkov najmenší prvok a presunie ho na začiatok.
Výpočtová zložitosť tohto algoritmu je . Vo všeobecnosti je rýchlejší ako bubble-sort, avšak pomalší ako insertion-sort.
Insertion-sort
Insertion-sort (triedenie priamym vkladaním) používa jednu časť triedeného poľa pre ukladanie už vytriedených hodnôt a druhú časť toho istého poľa pre hodnoty ktoré ešte nemajú správne poradie. Princíp je podobný ako pri selection-sorte.
Časová výpočtová zložitosť je . Avšak narozdiel od selection-sortu, rýchlosť insertion-sortu závisí od vstupného poľa – pre takmer utriedené pole prebehne veľmi rýchlo.