Triedenie porovnávaním

Algoritmy uvedené v predchádzajúcom texte určujú poradie prvkov iba na základe vzájomného porovnávania vstupných prvkov. Preto sa aj volajú triedenia porovnávaním. Dá sa dokázať, že každé triedenie porovnávaním musí v najhoršom prípade na utriedenie postupnosti n čísel vykonať Veľká-Omega(n lg n) porovnaní. Teda mergesort a heapsort sú asymptoticky optimálne a neexistuje žiadne triedenie porovnávaním, ktoré by bolo rýchlejšie ako o konštantný faktor.

Triedenie v lineárnom čase

Existujú však algoritmy, ktoré majú časovú zložitosť lepšiu ako O(n lg n), predpokladajú však, že vstupné dáta majú isté špeciálne vlastnosti. Používajú teda iné nástroje ako porovnávanie na utriedenie prvkov. Taktiež nepracujú na mieste, ale potrebujú extra pamäť. Príklady takýchto algoritmov sú Counting sort, Bucket sort a Radix sort. Counting sort and Radix sort predpokladajú, že vstup sa skladá z celých čísel z nejakého malého rozsahu. Bucket sort predpokladá, že vstup je generovaný náhodným procesom a distibuje jednotlivé prvky náhodne po celom intervale.

Napriek lineárnej časovej zložitosti nie sú tieto algoritmy veľmi použiteľné v praxi z nasledujúcich dôvodov:
 a) Efektívnosť týchto triediacich algoritmov závisí na náhodnom usporiadaní prvkov. Ak táto podmienka nie je splnená, výsledkom je ich znížený výkon.
 b) Pre beh algoritmov je potrebná pamäť navyše – až do veľkosti usporadúvaného poľa. Ak je triedené pole veľmi veľké, predstavuje to problém.
 c) Vnútorné cykly týchto triedení obsahujú veľa inštrukcií, takže hoci sú lineárne, často nie sú rýchlejšie ako Quicksort.
^ TOP