Skip to main content.

Zaradenie a popis

Radix sort je triediaci algoritmus, ktorý pracuje v čase O(n). Používa inú metódu triedenia ako triedenie porovnávaním. Utriedi vstupné hodnoty podľa jednotlivých číslic. Ak začína od poslednej (najmenej dôležitej) tak hovoríme o LSD (least significant digit) variácii Radix sortu. Podobne, ak sa najprv triedi podľa prvej číslice, je to MSD (most significant digit) Radix Sort. Po skončení je vstupné pole utriedené. Radix sort využíva na utriedenie časti dát iný algoritmus triedenia (najčastejšie Counting Sort) a od vlastností tohto algoritmu závisí, či je Radix sort stabilné triedenie.

Radix sort má uplatnenie často pri triedení záznamov, ktoré ako kľúč používajú viacero položiek. Ak chceme napríklad utriediť dátumy podľa roku, mesiaca a dňa, štandardným porovnávaním by sme najprv porovnali roky, ak by nastala zhoda, porovnali by sme mesiace a ak by tiež nastala zhoda, porovnali by sme dni. Iný spôsob je použiť na triedenie myšlienku Radix sortu. Utriedime najprv položky podľa dňa, potom podľa mesiaca a nakoniec podľa roku.

^ TOP

Myšlienka algoritmu

Na prvý pohľad je triedenie Radix sortom nelogické. Utriedia sa vstupné prvky podľa poslednej číslice. Vstupná postupnosť sa teda rozdelí na desať podpostupností, kde všetky čísla končia rovnakou číslicou. Každú podpostupnosť následne utriedime podľa predposlednej číslice. Proces sa opakuje, až kým nie je vstup utriedený podľa všetkých číslic. Ak sú čísla rôzne dlhé, doplnia sa zľava nulami.

^ TOP

Vizualizácia

Radixsort Radixsort

^ TOP

Zápis algoritmu

    for i:=1 to d do
      utrieď stabilným triedením podľa cifry i
^ TOP

Vlastnosti algoritmu

Časová zložitosť algoritmu závisí od použitého pomocného stabilného triedenia. Najčastejšie je používaný Counting sort - ak sú čísla v rozsahu 1..k a k nie je príliš veľké. Zložitosť algoritmu sa dá vyjadriť ako Theta(nd+kd), kde n je veľkosť vstupu (počet čísel na utriedenie), k je rozsah hodnôt vstupu a d je počet cifier podľa ktorých sa triedi. Ak je d konštanta a k=O(n), tak čas behu algoritmu je O(n).

^ TOP

Experimentovanie

Department of Computer Science, University of British Columbia, Canada
Java applety rôznych triediacich algoritmov.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Department of Computer Science, University of Massachusetts Amherst, USA Radix sort ako applet.
http://www.cs.umass.edu/~immerman/cs311/applets/vishal/RadixSort.html

^ TOP