Avtor: Matjaž OMAN
Visokošolski strokovni študij Praktična matematika
Študijsko leto 2004/05
Viri: Robert Sedgewick Algorithms in Java (Part 1-4), third edition
Kadar želimo urejati podatke, kjer je ključ, ki definira urejenost podatkov zelo zapleten, lahko uporabimo zelo učinkovito metodo urejanja po delih. Metodo urejanja po delih uporabljamo, kadar lahko ključ razbijemo na dele fiksne dolžine (bite, znake, cifre). Urejanje po delih lahko uporabljamo v mnogih primerih: iskanje telefonskih naročnikov v telefonskem imeniku, urejanje igralnih kart, ...
| RadixLSD.java |
public static void lsd(String[] nizi, int L, int R, String zaporedje) {
String[] temp=new String[nizi.length];
// ureja od najbolj desnega proti najbolj levemu znaku
for (int znak=R-1; znak>=0; znak--) {
// tabela za stetje znako v nizih
int[] count=new int[zaporedje.length()+1];
int i;
for (i=0; i < zaporedje.length()+1; i++) count[i]=0;
// steje znake v nizih
for (i=L; i < nizi.length; i++) {
char c = nizi[i].charAt(znak);
count[zaporedje.indexOf(c)+1]++;
}
// zaporedoma pristeva stevilo znakov
for (i = 1; i < zaporedje.length()+1; i++)
count[i] += count[i-1];
// uredi znake z metodo urejanje s stetjem (key-indexed counting)
for (i = L; i < nizi.length; i++) {
char c = nizi[i].charAt(znak);
temp[count[zaporedje.indexOf(c)]++] = nizi[i];
}
// uredi nize
for (i = L; i < nizi.length; i++)
nizi[i] = temp[i - L];
}
}
|
Primer uporabe urejanja po delih, kjer so ključi sestavljeni iz znakov ASCII tabele. RadixLSD_Test.java (RadixLSD.java)
Če za urejanje posameznih mest ključev uporabimo urejanje s štetjem (key-indexed counting) je časovna zahtevnost tega dela algoritma enaka k=O(i), pri čemer je i število mest v ključih. V tem primeru je časovna zahtevnost celotnega algoritma enaka O(R*n + R*i). In če je R konstanta je časovna zahtevnost celotnega algoritma linearna O(n).