Triedenie

Pod triedením rozumieme proces preusporiadania danej množiny objektov v špecifickom poradí. Účelom triedenia je uľahčiť neskoršie vyhľadávanie prvkov triedenej množiny. Teda usporiadanie postupnosti objektov
a1, a2, ..., an, kde n >=1
do postupnosti
ai1, ai2, ..., ain
tak, aby platila relácia usporiadania <=
aij<=aij+1 pre j=1..n-1

V postupnosti sa môžu vyskytnúť aj také objekty, ktoré sú si rovné vzhľadom na reláciu usporiadania, teda pre ktoré platí: ak = am. Metóda triedenia sa nazýva stabilná, keď nezmení relatívnu postupnosť zhodných objektov, teda ak j<k a aj=ak, a ak sa aj nachádza po triedení na mieste is a ak na mieste it, tak is< it. Stabilita je dôležitá, ak sú objekty predtriedené vzhľadom na inú reláciu usporiadania (napríklad podľa určitých sekundárnych kľúčov – vlastností, ktoré samotný primárny kľúč neodráža).

^ TOP

Vlastnosti

Rozlišujeme taktiež medzi vnútornými a vonkajšími metódami triedenia. Ak sa pri triedení nepoužíva externá pamäť, hovoríme o vnútornej metóde triedenia, alebo o triedení in-situ (na mieste). Ak prevažná časť dátového súboru zostane počas triedenia v externej pamäti, hovoríme o vonkajšej metóde triedenia. Typickými vnútornými metódami sú bublinkové triedenie, bucketsort, quicksort, triedenie vkladaním a triedenie haldou. Triedenie zlučovaním je vonkajšia triediaca metóda.

^ TOP

Časová zložitosť

Na triedenie n objektov potrebuje všeobecná metóda triedenia, ktorá získava informácie o usporiadaní triedených prvkov len z operácií porovnávania medzi prvkami, v najhoršom prípade O(n.log2n) porovnaní.
Dobré meralo efektívnosti je tiež počet potrebných porovnaní kľúčov C a počet presunov prvkov M. Tieto počty sú funkciami poču n prvkov, ktoré sa majú triediť.

^ TOP

Triedenie poľa prvkov

Pole je postupnosť prvkov rovnakého druhu. Pri triedení usporadúvame pre jednotlivé objekty ich kľúče, ktoré sú tiež všetky rovnakého druhu. Preto je pole kľúčov vhodnou abstrakciou, nad ktorou môžme uvažovať ľubovolný triediaci problém.

^ TOP