Tento článek vznikl jako reakce na diskuzi v javovské konferenci konference@java.cz v listopadu 2009. Předmětem diskuze zde bylo řazení podle ČSN 97 6030. V dalším textu se nebudeme této normy striktně držet. Cílem článku není popsat implementaci řazení podle normy, ale spíše ukázat možnosti, které máme v Javě k dispozici pro abecední řazení řetězců.

Chceme-li seřadit množinu řetězců, musíme umět řetězce porovnávat. Tj. musíme umět rozhodnout, zda je jeden řetězec "menší než" druhý. Při porovnávání dvou řetězců postupujeme po znacích zleva doprava a znaky v jednom řetězci srovnáváme se znaky na stejné pozici ve druhém řetězci. Uspořádání českých znaků definuje česká abeceda:

a, á, b, c, č, d, ď, e, é, ě, f, g, h, ch, i, í, j, k, l, m, n, ň, o, ó, p, q, r, ř, s, š, t, ť, u, ú, ů, v, w, x, y, ý, z, ž.

Rozlišujeme tzv. primární, sekundární a terciární řadicí platnost znaků. Primární řadicí platnost mají znaky

a, b, c, č, d, e, f, g, h, ch, i, j, k, l, m, n, o, p, q, r, ř, s, š, t, u, v, w, x, y, z, ž.

Sekundární řadicí platnost mají znaky

á, ď, é, ě, í, ň, ó, ť, ú, ů, ý.

Nejprve hledáme rozdílné znaky s primární řadicí platností. Znaky se sekundární řadicí platností nahradíme pro tuto fázi znaky bez diakritiky (á nahradíme a, ď nahradíme d, atd.) a nepřihlížíme k rozdílům ve velikosti písmen (a je stejné jako A, b jako B, atd.). Pokud najdeme různé znaky s primární řadicí platností, je uspořádání řetězců dáno první (tj. nejlevější) dvojicí takových znaků. Např. slovo drak bude před slovem vlak, protože d je v abecedě před v, slovo kanoe bude před slovem kánon, protože e je před n a s á se v této fázi pracuje jako s a a slovo káď bude před slovem kat, protože d je před t (s ď pracujeme jako s d). Pokud nenajdeme rozdíly ve znacích s primární řadicí platností a řetězce mají různou délku, bude kratší řetězec před delším. Např. slovo kůň bude před slovem kuna, protože ů a ň mají sekundární řadicí platnost. Jsou-li řetězce stejně dlouhé, hledáme rozdíly ve znacích se sekundární řadicí platností, přičemž opět nepřihlížíme k rozdílům ve velikosti písmen. Uspořádání řetězců je, stejně jako u znaků s primární řadicí platností, dáno první dvojicí rozdílných znaků. Např. slovo kanón bude před slovem kaňon, protože n je v abecedě před ň.

Nenajdeme-li rozdíly ve znacích s primární ani sekundární řadicí platností, hledáme rozdíly ve velikosti písmen (terciární řadicí platnost). Velká písmena obvykle řadíme před malá. Např. slovo Brod bude před slovem brod.

Písmena z jiných národních abeced obvykle řadíme takto:

à, â, ä, ą, ç, è, ê, ľ, ł, ô, ö, ŕ, ü, ż.

Číslice řadíme podle jejich číselné hodnoty za poslední písmeno abecedy. Mají primární řadicí platnost. Skupiny číslic řadíme podle číselné hodnoty číslic. Např. 2 bude před 21 a to bude před 3.

Písmena některých abeced, např. řecké a azbuky, řadíme podle přepisu do české abecedy. Např. α přepisujeme jako alfa.

Mezeru řadíme před první znak abecedy. Další znaky řadíme za číslice obvykle v tomto pořadí:

  • interpunkční znaménka,
  • všechny tvary uvozovek,
  • ustálené značky,
  • matematické symboly.

Řazení v Javě

K řazení řetězců podle pravidel národních abeced slouží v Javě třídy Collator a RuleBasedCollator z balíku java.text.

List<String> p = ...;
Collator c = Collator.getInstance(new Locale("cs"));
Collections.sort(p, c);

Metoda Collator.getInstance vrátí instanci třídy RuleBasedCollator. Nevýhodou tohoto způsobu řazení je, že jsou ignorovány mezery a velká písmena jsou řazena za malá. Např. ulice Na Zbořenci bude řazena za ulicí Navrátilova a městská část Újezd bude za slovem újezd.

Třída RuleBasedCollator používá při porovnávání řetězců uspořádání znaků, které dostane jako parametr do konstruktoru. Uspořádání znaků definujeme pomocí relace "menší než", přičemž máme na výběr mezi primární, sekundární a terciární relací. Primární relaci definujeme pomocí menšítka (<), sekundární pomocí středníku (;) a terciární pomocí čárky (,). Např.

  • x<y definuje primární relaci mezi znaky x a y,
  • i;í definuje sekundární relaci mezi znaky i a í,
  • T,t definuje terciární relaci mezi znaky T a t.

Tyto relace lze kombinovat. Např. A,a;Á,á<B,b říká, že

  • A je menší než a (terciární relace),
  • Á je menší než á (terciární relace),
  • B je menší než b (terciární relace),
  • A, a jsou menší než Á, á (sekundární relace),
  • A, a, Á, á jsou menší než B, b (primární relace).

 

Pomocí těchto relací můžeme definovat uspořádání všech znaků, které se vyskytují v řazených řetězcích. Uspořádání písmen může vypadat takto:

"< A,a;Á,á;À,à;Â,â;Ä,ä;Ą,ą < B,b < C,c;Ç,ç < Č,č < D,d;Ď,ď < E,e;É,é;È,è;Ê,ê;Ě,ě < F,f < G,g < H,h < CH,Ch,cH,ch < I,i;Í,í < J,j < K,k < L,l;Ľ,ľ;Ł,ł < M,m < N,n;Ň,ň < O,o;Ó,ó;Ô,ô;Ö,ö < P,p < Q,q < R,r;Ŕ,ŕ < Ř,ř < S,s < Š,š < T,t;Ť,ť < U,u;Ú,ú;Ů,ů;Ü,ü < V,v < W,w < X,x < Y,y;Ý,ý < Z,z;Ż,ż < Ž,ž"

Mezeru zařadíme před první písmeno:

"< ' ' < A,a..."

Za poslední písmeno abecedy přidáme číslice, interpunkční znaménka, uvozovky a další symboly:

"< 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < '.' < ',' < ';' < '?' < '¿' < '!' < '¡' < ':' < '\"' < '\'' < '«' < '»'..."

Český komparátor tedy může vypadat takto:

public class CzechComparator implements Comparator<String> {
private static String rules =
"< ' ' < A,a;Á,á;À,à;Â,â;Ä,ä;Ą,ą < B,b < C,c;Ç,ç < Č,č < D,d;Ď,ď < E,e;É,é;È,è;Ê,ê;Ě,ě" +
"< F,f < G,g < H,h < CH,Ch,cH,ch < I,i;Í,í < J,j < K,k < L,l;Ľ,ľ;Ł,ł < M,m < N,n;Ň,ň" +
"< O,o;Ó,ó;Ô,ô;Ö,ö < P,p < Q,q < R,r;Ŕ,ŕ < Ř,ř < S,s < Š,š < T,t;Ť,ť" +
"< U,u;Ú,ú;Ů,ů;Ü,ü < V,v < W,w < X,x < Y,y;Ý,ý < Z,z;Ż,ż < Ž,ž" +
"< 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9" +
"< '.' < ',' < ';' < '?' < '¿' < '!' < '¡' < ':' < '\"' < '\'' < '«' < '»'" +
"< '-' < '|' < '/' < '\\' < '(' < ')' < '[' < ']' < '<' < '>' < '{' < '}'" +
"< '&' < '¢' < '£' < '¤' < '¥' < '§' < '©' < '®' < '%' < '‰' < '$'" +
"< '=' < '+' < '×' < '*' < '÷' < '~'";
private RuleBasedCollator comparator = new RuleBasedCollator(rules);
public CzechComparator() throws ParseException {
}
public int compare(String s1, String s2) {
return comparator.compare(s1, s2);
}
}

Přepis písmen z jiných abeced zajistíme pomocí návrhového vzoru Dekorátor. V metodě compare dekorátoru nejprve nahradíme každé písmeno jeho přepisem (např. "α" přepíšeme na "alfa") a pak přepsané řetězce porovnáme pomocí českého komparátoru. Pokud český komparátor vyhodnotí řetězce jako stejné, porovnáme původní řetězce pomocí sekundárního komparátoru, který řadí řecká písmena před jejich přepis (např. "β částice" bude před "beta částice") a řecké písmeno "σ" (sigma) řadí před "ς" (sigma).

V kódu pozor na rozdíl mezi písmenem o a řeckým omicron. Ačkoliv vypadají stejně, jde o dva rozdílné znaky. Písmeno o je v tabulce Unicode na pozici 006f a omicron je na pozici 03bf.

public class GreekLetters implements Comparator<String> {
private static String[] greek = {
"α", "β", "γ", "δ", "ε",
"ζ", "η", "θ", "ι", "κ",
"λ", "μ", "ν", "ξ", "ο",
"π", "ρ", "σ", "ς", "τ",
"υ", "φ", "χ", "ψ", "ω"
};
private static String[] transcript = {
"alfa", "beta", "gamma", "delta", "epsilon",
"zéta", "éta", "théta", "ióta", "kappa",
"lambda", "mí", "ný", "ksí", "omicron",
"pí", "rhó", "sigma", "sigma", "tau",
"upsilon", "fí", "chí", "psí", "omega"
};
private static String rules =
// alfa beta gamma delta epsilon
"< 'α' < a < 'β' < b < 'γ' < g < 'δ' < d < 'ε' < e" +
// éta fí chí ióta kappa
"< 'η' < é < 'φ' < f < 'χ' < ch < 'ι' < i < 'κ' < k" +
// ksí lambda mí ný omega omicron
"< 'ξ' < k < 'λ' < l < 'μ' < m < 'ν' < n < 'ω' < 'ο' < o" +
// pí psí rhó sigma sigma
"< 'π' < 'ψ' < p < 'ρ' < r < 'σ' < 'ς' < s" +
// tau théta upsilon zéta
"< 'τ' < 'θ' < t < 'υ' < u < 'ζ' < z";
private Comparator<String> decoratee;
private RuleBasedCollator secondaryComparator = new RuleBasedCollator(rules);
private Map<String, String> cache = new HashMap<String, String>();
public GreekLetters(Comparator<String> decoratee) throws ParseException {
this.decoratee = decoratee;
}
String transcribe(String s) {
String p = cache.get(s);
if (p == null) {
p = s;
for (int i = 0; i < greek.length; i++) {
p = p.replaceAll(greek[i], transcript[i]);
}
cache.put(s, p);
}
return p;
}
public int compare(String s1, String s2) {
String t1 = transcribe(s1);
String t2 = transcribe(s2);
int c = decoratee.compare(t1, t2);
if (c != 0) {
return c;
}
return secondaryComparator.compare(s1, s2);
}
}

Chcete-li si tento kód vyzkoušet, stáhněte si zdrojáky nebo jar s přeloženými třídami. Jar pustíte takto:

java -jar Sorting.jar inputFile outputFile

Ve vstupním souboru budou řetězce, které chceme seřadit, vždy jeden řetězec na řádku. Např.:

Nad Popelkou
Nad Santoškou
náměstí Kinských
Na Pláni
Nad Klamovkou
Na Hřebenkách

Výstupní soubor bude obsahovat uspořádané řetězce:

Na Hřebenkách
Na Pláni
Nad Klamovkou
Nad Popelkou
Nad Santoškou
náměstí Kinských