Triediace algoritmy Bubble-sort, Quick-sort, Merge-sort, Select-sort, Heap-sort, Insert-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.