Saturday, June 25, 2011

SW: Radix Sort

- tzv. priehradkove radenie
- pouziva jednotlive zlozky hodnoty, znaky, bity apod.
- napriklad od LSB radi kazdy polozku do priehradok, v jednej priehradke bude vsetko s a na konci, v druhej s b, v tretej c. prepojene to je ako spojovy zoznam.
- potom sa spravi poriadok podla 2 pismenka, pricom sa znovu priehradkuje, alebo teda polozky sa presuvaju z priehradok do inych priehradok podla pismenka. Tie, co boli v priehradke a po prvom radeni, zostanu na vrchu, tie co boli v b budu druhe v poradi, ale napriklad v priehradke pre b
- potom podla 3ieho
- atd. az kym nemame hotovo

- kedze to je spojovy zoznam, tak presuvanie je velmi rychle, pretoze len presuvame pointre
- zlozitost theta(dn), kde d je dlzka najdlhsieho prvku (napr. pocet pismen)