Urejanje po delih (radix sort)


Glavna stran

Uvod

Pogosto želimo urejati zapise kjer so ključi, ki definirajo razpored zapisov, zelo zapleteni. Na primer: kompleksnost ključev v telefonskem imeniku ali katalogu v knjižnici. Obdelava celega ključa na vsakem koraku je pogosto nepotrebna: pri iskanju telefonskih številk pogledamo samo prvih nekaj črk imena in že lahko najdemo stran na kateri je iskana številka. V takih primerih algoritme za urejanje izboljšamo tako, da razčlenimo ključe v zaporedje delov fiksne dolžine. Binarna števila so zaporedja bitov, nizi (string) so zaporedja znakov, decimalna števila so zaporedja cifer. Urejanje, ki obdeluje en ključ naenkrat, se imenuje urejanje po delih (radix sort).

Pri urejanju po delih (radix-sort) so deli ključev fiksne dolžine, tako da ima vsak del fiksno število različnih vrednosti. Ponavadi cela števila (0,1,2, ..., R-1) predstavljajo R različnih možnih vrednosti za vsak del. Torej ti algoritmi ravnajo s ključi kot s števili, ki so predstavljena kot osnovna (bazna) R števila za različne vrednosti R in delajo s posameznimi ciframi v številih.

Na primer: ko stroj na pošti obdeluje kup paketov, ki so označeni s 5-mestnimi števili, jih razporedi na deset kupov: eden ima števila, ki se začnejo z 0, naslednji ima števila, ki se začnejo z 1 in tako naprej. Kupi se lahko obdelujejo posamezno, z uporabo metode naslednje cifre ali pa s kakšno lažjo metodo, če paketov ni preveč. Če bi izbirali pakete iz kupov v zaporedju od 0 do 9 tako kot so bili obdelani, bi dobili urejeno razporeditev. Tak postopek predstavlja urejanje po delih (radix sort) z R=10 in je glavna metoda v aplikacijah kjer so ključi sestavljeni iz 5 do 10 mestnih števil kot so poštne številke, telefonske številke oz. številke zdravstvenega zavarovanja. Različne vrednosti dela (radix) R so primerne v različnih aplikacijah. Za cela števila, ki so v računalnikih predstavljena kot binarna, najpogosteje uporabljamo R=2 ali pa kvadriranje, ker nam to omogoči razstavljanje ključev v neodvisne dele. Za ključe, ki vsebujejo nize (string) uporabljamo R=28 ali R=216. Poleg specifičnih aplikacij, lahko obravnavamo karkoli je predstavljeno znotraj računalnika kot digitalno število.