Radiks sortiranje

	Radiks sortiranje
Namena	sortiranje
Struktura podataka	niz
Vremenska kompl.	O(kn) do O(n logn)

Radiks sort (engl. Radix sort) je algoritam sortiranja koji koristi pozicionu reprezentaciju i odvojeno analizira cifre (ili znakove) na različitim pozicijama. Za demonstraciju ideje algoritma, bez gubitka opštosti, pretpostavlja se da su ključevi decimalni brojevi sa istim brojem od k cifara d_k-1 d_k-2 .. d₀.

Osnovna ideja[uredi | uredi izvor]

Osnovna ideja je razdvajanje brojeva u 10 grupa na osnovu vrednosti prve, najstarije cifre d_k-1. Time se izvrši grubo sortiranje jer je svaki broj iz grupe koja odgovara manjoj prvoj cifri manji od brojeva iz grupa koje odgovaraju većoj prvoj cifri. Zatim se izvrši sortiranje u okviru svake grupe na po 10 podgrupa u zavisnosti od vrednosti druge cifre d_k-2. Postupak se rekurzivno nastavlja i završava u k koraka, pri čemu je poslednji korak sortiranje po najmlađoj cifri d₀, posle čega je ulazni niz sortiran.

Implementacija[uredi | uredi izvor]

Iako je princip konceptualno jednostavan, pravolinijska implementacija bi bila dosta teška zbog toga što ovim procesom nastaje sve veći broj sve manjih grupa o kojima treba voditi evidenciju, što se ne može uraditi na neki posebno efikasan način. Prema tome, treba zadržati jednostavnost osnovne ideje, a postupak modifikovati tako da i implementacija bude efikasna. Efikasna implementacija se može postići ako se započne tako što se u prvom koraku vrši sortiranje po najmlađoj cifri. Uzimaju se redom elementi iz neuređenog niza i razvrstavaju se u deset redova Q₀ $\dots$ Q₉ po vrednosti najmlađe cifre, tako što se tekući element stavlja na kraj odgovarajućeg reda. Kad se tako obrade svi elementi, onda se svi redovi opet spoje u jedan niz po poretku Q₀ $\dots$ Q₉. U sledećem koraku se opet uzimaju elementi ovog niza redom i razvrstavaju u redove, ali po vrednosti druge cifre d₁, pa se opet na kraju svi redovi spoje. Postupak se završava kad se izvrši uređenje i po najstarijoj cifri d_k-1.

Suština ovog algoritma je u stabilnosti procesa sortiranja, koja je omogućena ubacivanjem elemenata u red na njegov kraj. Prema tome, kada se u i-tom koraku vrši sortiranje po cifri d_i-1, veći je onaj element koji ima višu cifru na toj poziciji i on ide u odgovarajući red. Elementi sa istom cifrom idu u isti red, ali su oni zbog stabilnosti metoda već uređeni po nižim ciframa. Ovo omogućava spajanje redova bez vođenja računa o njihovim granicama.

Prilikom implementacije algoritma treba voditi računa o tome da se broj elemenata u redovima u pojedinim koracima ne može predvideti. Zato sekvencijalna realizacija redova nije pogodna, već se pribegava ulančanoj reprezentaciji. Redovi se održavaju kao ulančane liste u koje se novi elementi stavljaju na kraj. Zbog toga je za svaki red potrebno obezbediti pokazivače koji pokazuju na početak i kraj liste. Na početku se od neuređenog niza napravi jedna lista iz koje se uzimaju elementi i stavljaju u redove. Posle svakog koraka sve liste se opet nadovezuju u jednu listu, počevši od liste koja odgovara cifri 0 do cifre koja odgovara cifri 9.

Primeri[uredi | uredi izvor]

Prvi primer[uredi | uredi izvor]

Uzmimo za primer da treba da sortiramo niz 213 191 222 214 koristeći radiks sort. Prvi korak:

191 222 213 214

Drugi korak:

213 214 222 191

Treći korak:

191 213 214 222

Drugi primer[uredi | uredi izvor]

Sortiramo radiks sortom trocifrene brojeve 329, 457, 657, 839, 436, 720, 355. Prvi korak:

Drugi korak:

Konačno:

Performanse[uredi | uredi izvor]

Vremenska složenost metoda zavisi od broja cifara k i od broja elemenata n. Kako se u svakom od k koraka obrađuju svi elementi, vremenska složenost je reda $O(kn)$ . Ako je broj cifara k konstantan, onda je složenost linearna. Zbog linearne složenosti ovo je vrlo efikasan metod za kratke ključeve. Ukoliko su ključevi dugački, performansa opada, pa se tada najčešće koristi usvojiti neko hibridno rešenje. Princip radiks sortiranja se može primeniti samo na manji broj najstarijih cifara, što daje nepotpuno sortiraran niz, ali donekle uređen. Završno sortiranje se tada obavlja nekim metodom koji je efikasan za prilično uređene nizove, kao što je direktno umetanje.

Ako k nije konstanta već raste sa n, onda se povećava i vremenska složenost. Na primer, ako su ključevi gusti, pa skup ključeva pokriva skoro čitav skup mogućih vrednosti, onda se k približava $logn$ , a složenost se približava $O(nlogn)$ .