Pod pojmem řazení se rozumí takové přeuspořádání struktury, aby její prvky tvořily monotónní posloupnost. Často se též používá méně správný výraz třídění. Srdcem každého řadicího algoritmu [1], [2] je příkaz k porovnání dvou prvků. Je-li kritériem monotónnosti (třídicím klíčem) číslo, je porovnání triviální. Podívejme se na obtížnější případ, kdy se mají porovnávat textové řetězce obsahující znaky s diakritickými znaménky.
Procesory Intel mají pro porovnávání řetězců strojovou instrukci
REP CMPS, ta však porovnává podle pořadí znaků, v jakém jsou
definovány v použité kódové stránce, tedy nesprávně.
Způsob řazení, které se v praxi používá ve slovnících, rejstřících a lepších
programech, u nás kodifikuje státní norma [3]. Vzhledem
k obtížné algoritmizovatelnosti některých požadavků normy se v osobních
počítačích zpravidla implementuje zjednodušená varianta, viz
[4], [5], [6], [7].
Pořadí písmen určuje v první řadě jejich sémantika, nikoli jejich kódová hodnota v tabulce ASCII. To znamená, že slovo začínající písmenem A bude řazeno před slovo začínající B bez ohledu na to, je-li zapsáno jako velké či malé a má-li čárku, přehlásku nebo jiné diakritické znaménko. Oba porovnávané řetězce je tedy nutno nejprve převést do redukované abecedy, která stírá rozdíly ve velikosti písmen a odstraňuje diakritiku. Kromě 10 číslic a 26 písmen obsahuje redukovaná abeceda ještě čtyři souhlásky s háčkem ČŘŠŽ, které mají také primární řadicí platnost. Po překódování do této omezené abecedy již lze oba řetězce porovnat strojově podle kódových hodnot znaků redukované abecedy. Není podstatné, jakým znakům v ASCII tabulce odpovídá překódovaný text, důležitá je jen jejich relativní hodnota - řadicí váha.
| Řazené slovo | Stav po I.vážení |
Výsledné pořadí |
|---|---|---|
| sije | SIJE | 1. |
| šije | ŠIJE | 2.? |
| šíje | ŠIJE | 2.? |
| Šíje | ŠIJE | 2.? |
Jsou-li po převodu do redukované abecedy oba řetězce různé, je tím jejich pořadí určeno, jinak musíme uplatnit jemnější kritérium, kterým jsou diakritická znaménka. Velikost písmen se v této druhé fázi ještě neuplatňuje. Výskyt diakritického znaménka zvyšuje řadicí váhu znaku takto:
| Řazené slovo | Stav po I.vážení |
Stav po II.vážení | Výsledné pořadí |
|---|---|---|---|
| sije | SIJE | SIJE | 1. |
| šije | ŠIJE | ŠIJE | 2. |
| šíje | ŠIJE | ŠÍJE | 3.? |
| Šíje | ŠIJE | ŠÍJE | 3.? |
Pokud ani ve druhém průchodu nedojde k určení pořadí, následuje transformace řetězců podle třetí tabulky vah, která již rozlišuje jak diakritiku, tak i velká a malá písmena. Pro zjednodušení se již v této třetí fázi obvykle rozlišují také nealfanumerické znaky.
| Řazené slovo | Stav po I.vážení |
Stav po II.vážení | Stav po III.vážení |
Výsledné pořadí |
|---|---|---|---|---|
| sije | SIJE | SIJE | sije | 1. |
| šije | ŠIJE | ŠIJE | šije | 2. |
| šíje | ŠIJE | ŠÍJE | šíje | 3. |
| Šíje | ŠIJE | ŠÍJE | Šíje | 4. |
K uspokojivému řazení tedy potřebujeme nejméně tři tabulky řadicích vah pro každé z možných kódování češtiny. Ruční sestavování takových tabulek je zdlouhavé, proto vznikl program SortKit, který je umí vygenerovat z uživatelsky mnohem příjemnějšího zadání požadovaného pořadí znaků. SortKit generuje nejen samotné váhové tabulky, ale rovnou celý zjednodušený trojfázový řadicí program, takže je snadné správnou funkci navrhované tabulky ihned po jeho kompilaci ověřit.
Ne všechny požadavky korektního řazení jsou splnitelné pouhou volbou vah a komplikují proto porovnávací algoritmus. Znaky ch,Ch a CH se v českém jazyce považují za dvojhlásky řazené mezi H a I. Pro zpracování této anomálie je třeba v porovnávací proceduře zavést pomocnou dvouznakovou proměnnou (v generovaných kódech je nazývána Diphtong), která si pamatuje právě načtený a předchozí znak a umožňuje tak detekovat dvojhlásky. V případě výskytu dvojice ch,Ch nebo CH se změní váha znaku c uložená v předchozím kroku za váhu znaku i. Místo váhy druhého písmene dvojhlásky (h) se uloží nejnižší možná váha 0, případně (je-li to třetí průchod) váha 0,1 nebo 2 podle velikosti dvojhlásky. Dvojice znaků cH se za dvojhlásku nepovažuje. Aby nedocházelo ke konfliktu takto "zvážené" dvojhlásky CH s případnou dvojicí imezera, program SortKit rezervuje první tři váhy jako postfix dvojhlásky a normálním znakům včetně mezery přiděluje váhy od 4 nahoru.
Jsou-li slova v porovnávaném řetězci oddělena více než jednou mezerou, mají se řadit tak, jako by byla oddělena právě jednou mezerou. Případné počáteční mezery se rovněž ignorují. K implementaci této vlastnosti lze využít výše zmíněnou proměnnou Diphtong, kterou na počátku překladu inicializujeme mezerami a načítané znaky ignorujeme, dokud jsou v této proměnné dvě mezery.
Cizojazyčná písmena by měla být řazena podle jejich fonetického přepisu do češtiny, např. řecké písmeno alfa α jako alfa, německé ostré ß jako ss apod. Tato vlastnost je v generovaných příkladech splněna jen částečně, přiřazením váhy odpovídající fonetickému ekvivalentu.
Někdy je vhodné při porovnávání určité znaky vynechávat. Například při sestavování rejstříku chceme mít hesla řazena bez ohledu na to, zda jsou či nejsou uzavřena v úhlových závorkách. Podle normy se ale závorky a podobné symboly mají řadit až za všechna písmena a číslice. Přiřaďme tedy znakům < a > v rozporu s normou řadicí váhu 0. Pokud porovnávací program bude znaky s nulovou vahou ignorovat, dostáváme očekávané pořadí podle následující tabulky:
| Řazené slovo | Po zvážení | Výsledné pořadí |
|---|---|---|
| <TABLE> | TABLE | 1. |
| TABULKA | TABULKA | 2. |
| <TBODY> | TBODY | 3. |
| TEXTY | TEXTY | 4. |
SortKit je pomocná utilita pro programátory, kteří potřebují implementovat
ve svých výtvorech české řazení. Pracuje jako kompilátor, který načítá
definice řadicích vah ze vstupního textového souboru a vytváří z nich
tabulku vah v syntaxi zvoleného cílového jazyka. Název vstupního souboru je
třeba zadat jako parametr, implicitní přípona je .DSW. Výstupem je
nejen samotná váhová tabulka trojfázového řazení, ale obsahuje i jednoduchou
implementaci bublinkového třídění včetně procedury pro porovnání textových
řetězců podle výše uvedených zásad.
Cílový programovací jazyk se volí parametrem z těchto možností:
| Parametr | Jazyk | Generovaná přípona |
Odladěno programem |
|---|---|---|---|
| /A | Assembler | .ASM | Turbo Assembler 2 |
| /N | Netwide Assembler | .NAS | NASMW 0.98 |
| /C | C | .C | Microsoft C/C++ 7.0 |
| /P | Pascal | .PAS | Turbo Pascal 5 |
| /B | - | .BIN | - |
Pozn. Varianta /N produkuje 32bitovou konsolovou aplikaci pro
Windows. K jejímu sestavení je kromě assembleru NASM [8]
zapotřebí knihovník ALIB [9] a linker ALINK
[10], vše freeware.
Při použití parametru /B se negeneruje zdrojový kód, ale pouze
binární data tabulky vah. Výstupní soubor má délku 3*256=768.
Pokyny ke kompilaci jsou uvedeny jako poznámka v záhlaví cílového programu. Nevybereme-li žádný cílový jazyk, SortKit provede pouze syntaktickou kontrolu vstupního souboru. Cílový soubor má název shodný se vstupním souborem, jen přípona .DSW je změněna podle zvoleného programovacího jazyka.
Dalšími parametry programu SortKit lze volit kódování češtiny použité v komentářích výsledného programu:
| Parametr | Kódování komentářů |
|---|---|
| /ISO | ISO-8859-2 |
| /KAM | CP895 Kamenických |
| /LAT | CP852 PC Latin2 |
| /WIN | CP1250 Windows CE |
Bez ohledu na zvolené kódování poznámek by uživatel měl zajistit, aby vstupní soubor obsahoval definice pouze těch znaků, které jsou obsaženy v kódu, pro který je tabulka zamýšlena. Vzorové definice vah přiložené v distribuci SortKit tento požadavek splňují, viz např. soubor VAHY1KAM.DSW.
Znaky se stejnou řadicí vahou musejí být definovány na jednom řádku. Mohou
být definovány dekadicky (0..255), hexadecimálně (0x00..0xFF nebo 00h..FFh)
nebo řetězcem ohraničeným apostrofy či uvozovkami. Definice na jednom řádku
se oddělují čárkou ',' nebo výpustkou '..'.
Zalamování řádků není podporováno, ale délka řádku není omezena a zápis lze
zkracovat používáním výpustek, které reprezentují souvislou řadu znaků
včetně krajních. Za definicí může být umístěna poznámka odělená
středníkem.
Příklad platného řádku:
"()",0x5B..0x5D,123..125 ; kulaté,hranaté,složené závorky a lomítka
Všechny znaky uvedené na prvním řádku dostanou řadicí váhu 0. Váhy 1 až 3
jsou rezervovány pro rozlišení dvojhlásek, takže znaky na druhém řádku
dostanou váhu 4, na třetím řádku 5 atd.
Zdrojový soubor musí obsahovat definice vah pro tři průchody, tabulka
každého průchodu musí být v souboru DSW zahájena řádkem obsahujícím
hvězdičku * v prvním sloupci.
V distribuci SortKit jsou přibaleny výchozí definiční soubory pro čtyři
nejběžnější kódování češtiny (soubory VAHY1???.DSW). Repertoár znaků
v českých kódových stránkách a jejich anglické názvy uvedené jako komentář
vycházejí z upravené definice Unicode [11],[12],[13],[16].
SortKit kontroluje správnost syntaxe zadaných znaků, jejich jedinečnost
v rámci každé ze tří tabulek a varuje při vynechání definice některého
z 3*256 znaků. Příklady chybových zpráv:
**Error** BADFILE.DSW(8) sloupec 6: chyba syntaxe.
*Warning* BADFILE.DSW(14) sloupec 10: vícenásobná definice znaku 17
*Warning* BADFILE.DSW(17) Tab.2: nedefinovaná váha znaku 252..255
Formát chybových hlášení programu SortKit je kompatibilní s Turbo Assemblerem pro snadnou integraci do programátorských editorů. Za názvem zdrojového souboru je v závorce uvedeno číslo chybného řádku, což např. při spouštění SortKitu z editoru MultiEdit [14] umožňuje automaticky nastavovat kurzor na chybný řádek zdrojového textu.
Tento program je volně šířitelný, za jeho používání nejsou vyžadovány žádné poplatky. Distribuce by měla obsahovat tyto soubory:
SORTKIT.COM kompilátor řadicích vah SORTKITC.HTM tento manuál SORTKIT.HTM anglický manuál VITSOFT.CSS stylopis k manuálu VAHY1ISO.DSW vzorové váhy pro kód ISO-8859-2 VAHY1KAM.DSW vzorové váhy pro kód CP895 Kamenických VAHY1LAT.DSW vzorové váhy pro kód CP852 DOS Latin 2 VAHY1WIN.DSW vzorové váhy pro kód CP1250 Windows VZOREK.TXT pro vyzkoušení správnosti řazení v kódu Kamenických VZOREKW.TXT pro vyzkoušení správnosti řazení v kódu Windows CP1250 CPP.ZIP úprava řadicího programu pro jazyk C++ FILE_ID.DIZ indentifikátor distribuce pro FTP/BBS
Nové verze SortKit hledejte na stránkách vit$oft freeware [15]. Tamtéž můžete získat univerzální řadicí program OKSORT, který umí využívat binární tabulky produkované utilitou SortKit a nemá omezení co do rozsahu řazených souborů.