Sortowanie leksykograficzne

Porządkowanie wyrazów przy tworzeniu słownika

W artykule tym nie będą omawiane mechanizmy sortujące wyrazy, wbudowane do wielu języków programowania. Student informatyki nie znajdzie tu wskazówek, jak rozwiązać zadanie domowe. Tematem będzie natomiast przygotowanie i wstępna obróbka danych przeznaczonych do posortowania. Zagadnienie to zainteresuje zapewne osoby chcące stworzyć słownik dowolnego języka tak, aby jednostki leksykalne były w nim posortowane tak, jak w prawdziwym słowniku drukowanym.

Wiele języków programowania, jak PHP czy JAVA, oferuje gotowe procedury sortujące tablice słów w porządku leksykograficznym, tj. takim, jak w słowniku. Nie będziemy tu próbowali analizować, jak w rzeczywistości działają takie procedury, wychodząc z założenia, że nie wyważa się otwartych drzwi: skoro armia ludzi przygotowała i zoptymalizowała odpowiednie algorytmy, nie ma sensu próbować pisać ich od nowa (chyba że miałoby to być ćwiczenie z umiejętności programowania). Zauważymy jednak, że wbrew pozorom stwarzanym często studentom na wykładach z informatyki trudno przy pomocy gotowych procedur posegregować posiadane dane tak, aby utworzyć z nich poprawny słownik. Zajmiemy się więc tutaj analizą rozmaitych pojawiających się problemów i zaproponujemy ich rozwiązanie.

Tekst i jego kodowanie

Przedmiotem sortowania leksykograficznego jest odpowiednio przygotowany tekst. Pracę sortującą wykonuje komputer, dlatego sortowany tekst musi być do niego dostarczony w postaci elektronicznej, to znaczy w postaci ciągów odpowiednich liczb. Mówiąc prościej, nie będziemy sortować wyrazów zapisanych na kartce papieru, ale raczej ich komputerowe odpowiedniki, będące w istocie ciągami liczb stanowiących kody używane przez komputer do przedstawienia liter i innych znaków pisma (nieliterowych). Odpowiednikiem kartki (czy książki) z zapisanymi wyrazami przeznaczonymi do posortowania jest dla systemu operacyjnego komputera odpowiedni plik danych.

Sortowane dane muszą być dostarczone w postaci na tyle czystej, na ile to możliwe. Plik danych nie powinien więc zawierać na przykład informacji o sposobie wyświetlania zawartości na ekranie, dołączanej przez procesory tekstu typu Word. Krótko mówiąc, nie możemy po prostu wziąć pliku doc czy pdf i poddać go działaniu procedury sortującej, gdyż w rezultacie otrzymalibyśmy coś, czego komputer nie umiałby zinterpretować.

Najlepiej sortować czysty tekst, taki jaki tworzony jest w edytorach typu Notatnik czy PSPad. Dodatkowo rozważać będziemy tekst sformatowany przy pomocy języka HTML. Okaże się bowiem, że pod pewnymi warunkami nie jest trudno sortować zawartość (ściśle określonego rodzaju) strony internetowej, i z pewnych względów takie sortowanie może mieć znaczenie praktyczne. Sortowanie widocznej w przeglądarce zawartości plików html musi jednak koniecznie zostać poprzedzone odpowiednimi przygotowaniami, o których będzie mowa niżej.

Najprostszym przykładem sortowania leksykograficznego rozważanego na zajęciach z informatyki jest sortowanie listy wyrazów o tej samej długości. Zagadnienie to, choć być może stanowiące dobry wstęp do bardziej zaawansowanych metod, pozbawione jest jednak jakiegokolwiek zastosowania praktycznego: nie istnieją języki, w których wszystkie wyrazy miałyby taką samą długość.

Drugim stopniem wtajemniczenia programisty jest sortowanie listy wyrazów o różnej długości. Zgodnie z zapowiedzią nie będziemy się tu w ogóle zajmować, na czym takie sortowanie w istocie polega. Zauważymy jednak, że przy pomocy procedury wbudowanej w używany przez nas język programowania może nie udać się nam uporządkować posiadanego wyciągu z leksykonu słownika danego języka, a to z co najmniej dwóch opisanych poniżej powodów.

Sortowanie listy haseł słownika a sortowanie wyrazów

Hasłem słownika wcale nie musi być pojedynczy wyraz graficzny. W słownikach języka polskiego często jako odrębne hasło figuruje wyrażenie na pewno, gdyż ułomne zasady pisowni łącznej i rozdzielnej każą je pisać jakby stanowiło dwa wyrazy. Nie będziemy tu dyskutować, dlaczego naprawdę piszemy łącznie, a na pewno oddzielnie, a tym bardziej skąd się wzięła różnica między codziennie a co dzień czy na co dzień. Zauważymy jedynie, że hasło słownika nie musi być równoznaczne z wyrazem, gdyż czasem hasło może stanowić także grupa wyrazów.

Sortować będziemy zatem listę haseł, a nie listę słów. Umówimy się, że całą listę danych, tj. listę haseł do posortowania, nazywać będziemy odtąd tablicą. Poszczególne hasła tej listy będziemy natomiast nazywać rekordami tej tablicy. Łatwo wyznaczyć koniec tablicy – będzie nim po prostu koniec pliku danych. Granicą rekordu będzie w najprostszym wypadku znak końca linii, a nie spacja oddzielająca wyrazy, gdyż dwa kolejne wyrazy (a nawet większa ich ilość) mogą wchodzić w skład jednego hasła. Granicą rekordu może też być przecinek lub średnik wraz z następującą spacją – w takim jednak wypadku musimy jakoś rozwiązać problem ostatniego rekordu (np. obowiązkowo dopisywać przecinek i spację na końcu pliku). Do problemu tego jeszcze wrócimy później.

W związku z tym pojawia się jednak pewien problem. Otóż część słowników stosuje następującą kolejność haseł: co, codziennie, codzienność, codzienny, co dzień, cofać, podczas gdy inne podają: co, co dzień, codziennie, codzienność, codzienny, cofać. W pierwszym rodzaju słowników spację oddzielającą wyrazy w obrębie hasła traktuje się tak, jakby nie istniała. W drugim typie spację traktuje się natomiast tak samo jak zwykłą literę, i przypisuje się jej najniższy możliwy kod (nadaje się spacji najniższy możliwy priorytet przy sortowaniu). Ten drugi sposób wypływa niejako automatycznie ze sposobu kodowania tekstu, w którym spacji przypisuje się kod 32. Posługuje się nim algorytm komendy sort zawartej w konsoli pseudo-DOS Windows XP.

Jeżeli zależy nam na zastosowaniu pierwszego z podanych sposobów, konieczna może się okazać pewna wstępna ingerencja w tekst, przy czym może ona dokonywać się ręcznie albo też może być elementem specjalnej procedury, którą musimy napisać samodzielnie i którą będziemy uruchamiać przed zastosowaniem wbudowanej funkcji sortującej. Istnieje z pewnością wiele rozwiązań pozwalających traktować spacje oddzielające wyrazy wewnątrz hasła jakby nie istniały, o ile oczywiście decydujemy się na takie właśnie rozwiązanie. W dalszym ciągu postaramy się znaleźć sposób, który przy okazji pozwoli zlikwidować cały szereg innych problemów związanych z sortowaniem.

Sortowanie tekstu ośmiobitowego zawierającego znaki narodowe

Komputery i ich systemy operacyjne stanowią w istocie wynalazek amerykański, i standardy w nich obowiązujące też dostosowane są przede wszystkim do amerykańskiej rzeczywistości. Jej elementem jest tzw. alfabet anglosaski, często błędnie nazywany łacińskim (alfabet łaciński nigdy nie zawierał litery W!). Litery tego alfabetu kodowane są tak, że kolejnym literom przypisywane są kolejne kody liczbowe. I tak, litera a otrzymuje kod 97, litera b – kod 98, litera c – 99 itd. W rzeczywistości więc zamiast wyrazów komputer sortuje ich reprezentacje. Zamiast wyrazu man komputer otrzymuje ciąg 109-97-110, zamiast bat – ciąg 98-97-116 itd. Procedura sortująca porównuje najpierw pierwszy kod sortowanych ciągów, w tym wypadku 109 i 98, a następnie ustawia liczbowe reprezentacje wyrazów tak, aby ustawić kody w pozycji rosnącej, a więc najpierw 98, a potem 109. Najpierw brane są pod uwagę i porównywane pierwsze liczby w ciągu, potem dopiero drugie – ale tylko wtedy, gdy pierwsze są takie same. Poprawna procedura sortująca ustawi także wyraz bat przed wyrazem bath. Brak litery na czwartej pozycji w wyrazie bat i brak jej kodu w reprezentacji liczbowej tego wyrazu spowoduje bowiem, że komputer potraktuje tę sytuację tak, jakby na czwartym miejscu znajdowało się zero. Należy jednak zaznaczyć, że nie wszystkie procedury sortujące poprawnie stosują tę zasadę. Takimi błędnie napisanymi procedurami nie będziemy się tu jednak w ogóle zajmować.

Bardziej skomplikowaną sytuację (i dlatego najczęściej zupełnie pomijaną w podręcznikach informatyki) mamy wówczas, gdy konieczne staje się posortowanie wyrazów języka polskiego. Przede wszystkim zacznijmy od przypomnienia, że nie istnieje jeden, powszechnie przyjęty standard kodowania polskich znaków. I tak, na przykład literze ą w zależności od przyjętego systemu kodowania (tzw. strony kodowej) przypisywane są bardzo różne wartości liczbowe. W systemie MacOS CE używa się kodu 136, w AmigaPL – kodu 226, w niegdyś popularnym systemie Mazovia (cp790) – kodu 134, w Latin-2 (cp852) – kodu 165, w Windows-1250 – kodu 185, wreszcie w ISO 8859-2, zwanym też ISO Latin-2 (w którym kodowany jest także tekst na tej witrynie) – kodu 177. Powoduje to pojawienie się dwojakiego rodzaju problemów.

Po pierwsze, dana procedura będzie poprawnie sortować tylko teksty zakodowane w ściśle określony sposób. Na przykład wyżej wzmiankowana komenda sort konsoli Windows XP posortuje nam poprawnie tylko plik tekstowy zakodowany w Latin-2. Istnieje bardzo wiele programów umożliwiających konwersję między systemami kodowania polskich znaków, niemniej jednak musimy pamiętać, że sortowanie pliku stworzonego w Notatniku wymagać będzie wstępnego przekodowania go do dosowej strony kodowej Latin-2. Rezultat pracy komendy sort również będziemy musieli przekodować z powrotem do strony kodowej Windows, jeśli mamy korzystać z niego w programach typu Notatnik.

Po drugie zauważmy, że kody liter uniemożliwiają stosowanie sortowania bez wstępnej obróbki, gdyż nie odpowiadają one wcale kolejności liter w alfabecie (zob. tabele poniżej). W ISO 8859-2 poprawna kolejność alfabetyczna a-ą-b-c-ć-d-… odpowiada kolejności 97-185-98-99-230-100-…, a więc niezgodnej z rosnącymi wartościami liczb będących kodami liter. Co więcej, „starszeństwo” kodów może się zmieniać zależnie od strony kodowej, np. w Latin-2 kod litery ą ma większą wartość niż kod litery ć, natomiast w ISO Latin-2 kolejność ta jest odwrotna, taka, jak w alfabecie.

Szesnastkowy układ liczbowy i kody liter w popularnych stronach kodowych

Komputery nie pracują w dziesiętnym, ale w dwójkowym systemie liczbowym. Przetwarzane dane przyjmują postać ciągów bitów, z których każdy może wystąpić tylko w dwóch stanach (zgaszony bądź zapalony). Bity z kolei grupowane są po osiem w bajty. Aby w wygodny sposób zapisywać rzeczywistą strukturę danych przetwarzanych przez komputer, w informatyce przyjęto posługiwać się systemem szesnastkowym. W systemie tym używa się nie tylko cyfr dziesiętnych 0-9, ale także liter A-F, którym umownie przypisuje się liczbowe wartości 10-15. Dla wartości 16, w systemie szesnastkowym użyjemy zapisu 10, co łatwo można odczytać jako jedna szesnastka i zero jedności. Aby nie pomylić takiego zapisu ze zwykłym, dziesiętnym, stosuje się szereg różnych metod, np. dopisuje się 0x przed liczbą, albo dopisuje na jej końcu literę h (od heksadecymalny = szesnastkowy). A zatem liczba 16 w systemie szesnastkowym to 0x10 lub 10h.

Każda cyfra w notacji szesnastkowej odpowiada czterem kolejnym bitom, a zatem na bajt przypadają dwie takie cyfry. Z uwagi na powszechność szesnastkowego układu liczbowego, od tej pory będziemy w nim podawać wszystkie kody znaków pisma. Ma to także taką zaletę, że od razu widać, ile bajtów potrzeba do zakodowania danego znaku. Z poniższych tabel widać więc, że takie systemy kodowania jak MacOS CE, AmigaPL, Mazovia, Latin-2, Windows-1250 czy ISO 9959-2 zadowalają się jednym bajtem, podczas gdy systemy unikodowe wymagają dwóch bajtów, przynajmniej do kodowania niektórych znaków. Problemem tym zajmiemy się nieco później.

Kody heksadecymalne małych liter alfabetu polskiego

MacOS CE

AmigaPL

Mazovia

Latin-2

Win-1250

ISO 8859-2

UTF-8

C4 85

C4 87

C4 99

C5 82

C5 84

Unicode

105

107

119

142

144

MacOS CE

AmigaPL

Mazovia

Latin-2

Win-1250

ISO 8859-2

UTF-8

C3 B3

C5 9B

C5 BA

C5 BC

Unicode

15B

17A

17C

Kody heksadecymalne dużych liter alfabetu polskiego

MacOS CE

AmigaPL

Mazovia

Latin-2

Win-1250

ISO 8859-2

UTF-8

C4 84

C4 86

C4 98

C5 81

C5 83

Unicode

104

106

118

141

143

MacOS CE

AmigaPL

Mazovia

Latin-2

Win-1250

ISO 8859-2

UTF-8

C3 93

C5 9A

C5 B9

C5 BB

Unicode

15A

179

17B

Alfabet

Różnego rodzaju studia i kursy programowania ograniczają się często do problemu sortowania leksykograficznego wyrazów zawierających wyłącznie małe litery alfabetu angielskiego (z zakresu a-z), co jest zadaniem stosunkowo prostym, gdyż wystarczy posortować kody tych liter. Jak widzieliśmy, problem komplikuje się, gdy wewnątrz rekordów (tj. haseł sortowanego leksykonu) pojawiają się spacje. Sortowanie tekstu zawierającego również litery polskie powoduje, że nie możemy już bezpośrednio odwoływać się do kodów liter, konieczny staje się alfabet, w którym litery mogą być uporządkowane inaczej niż sugerują ich kody, np. pomiędzy literą o kodzie 73h a literą o kodzie 74h wstawiamy jeszcze literę o kodzie B6h.

Innymi słowy, program do sortowania musi wiedzieć, jaka jest kolejność liter w używanym alfabecie. Co więcej, ważna jest nie kolejność liter, ale ich kodów liczbowych. A zatem aby posortować tekst polski zakodowany w ISO Latin-2, należy użyć innego alfabetu niż w wypadku sortowania tekstu zakodowanego w Latin-2. Pojęcie „alfabet” ma tu zatem znaczenie inne niż np. w szkole. O ile szkolny alfabet jest ciągiem liter (znaków), o tyle alfabet przeznaczony dla programu sortującego jest ciągiem określonych liczb… a przynajmniej takie (błędne) wrażenie osiągamy na obecnym etapie analizy problemu.

Problem sortowania nie sprowadza się zatem do porównania liter, gdyż komputery nie operują literami, ale ich kodami. Jednak tak naprawdę nie są nawet porównywane rzeczywiste kody liter, ale innego rodzaju kody, tworzone przez program sortujący, odpowiadające kolejności alfabetycznej. Literom a-ą-b-c-ć-d-… odpowiadają w ISO Latin-2 kody 61h-B1h-62h-63h-E6h-64h-…, a tym kodom z kolei przypisywane są kolejne liczby 1-2-3-4-5-6-…

Na przykład wyraz łąka zakodowany jest w tekście ISO Latin-2 jako B3h-B1h-6Bh-61h, jednak to nie ta postać podlega sortowaniu: wyraz ten zamieniony może być na sekwencję liczb 16-2-14-1 i dopiero taka (lub podobna) postać jest sortowana leksykograficznie.

Na końcu artykułu umieszczono przykłady alfabetów, w tym wszystkie wymienione w tekście. Zgodnie z konwencją obowiązującą w internecie, alfabety te zakodowane są w ISO Latin-2. Niektóre symbole literowe są złożone z części, o czym niżej.

Problem dużych liter

W przeciwieństwie do list słów przeznaczonych do ćwiczeń dla studentów informatyki, leksykon prawdziwego słownika zawiera (a w każdym razie może zawierać) także wyrazy pisane od dużych liter. Stwarzają one kolejny poważny problem przy sortowaniu.

Zauważmy, że dopóki tekst zawiera wyłącznie małe litery i spacje, przekształcenie go na ciąg kodów jest odwracalne. Program sortujący może zamiast oryginalnego ciągu znaków (a właściwie ich kodów) pobrać liczby odpowiadające ich kolejności w alfabecie, dokonać uporządkowania tak zakodowanych wyrazów, a następnie odtworzyć każdą pojedynczą literę z już uporządkowanego kodu. Ponieważ pozycja małej litery a i dużej litery A w alfabecie jest taka sama, program sortujący będzie musiał zapamiętać rekordy w oryginalnej postaci obok ich kodów, aby potem właściwy rekord wstawić niezmieniony w odpowiednim miejscu pliku wynikowego.

Struktura alfabetu

Tytuł tej części wygląda na bezsensowny, ale to oczywiście tylko pozory. Przypomnijmy, że chodzi nam o alfabet w szczególnym rozumieniu. Alfabetem jest dla nas nie lista odpowiednio ułożonych liter, ale funkcja przypisująca każdej z tych liter odpowiednią wartość liczbową, którą nazwiemy pozycją w alfabecie. Różnica jest istotna właśnie w momencie, gdy rozważamy problem małych i dużych liter.

Okazuje się bowiem, że alfabetu nie można napisać w postaci liniowej: aąbcćd…, bo wówczas w ogóle pominęlibyśmy duże litery. Zapis w rodzaju aAąĄbBcCćĆdD… też nie rozwiąże sprawy, bo przecież litery a i A powinny mieć przypisaną tę samą (pierwszą) pozycję w alfabecie. Można oczywiście tak skonstruować program, by dwóm kolejnym literom alfabetu przypisywać taką samą pozycję. Takie rozwiązanie nie jest jednak uniwersalne. Dokładniej jego wady staną się oczywiste w dalszej części, jednak już teraz przypomnijmy sobie kwestię spacji, która może być brana pod uwagę jakby była literą o najniższej pozycji w alfabecie (i dzięki temu co najmniej znajdzie się pomiędzy co a coby). Chodzi o to, że nie ma przecież małych i dużych spacji, i zasada przypisywania takiej samej pozycji dwóm kolejnym literom alfabetu musiałaby ulec modyfikacji dla pozycji równej zero, zarezerwowanej tylko dla spacji.

Pomińmy na razie kwestię spacji, trudnej do zilustrowania na przykładach, zajmijmy się jednak związanym z nią problemem. Można rozważać rozwiązanie, w którym każdej literze byłaby przypisana wartość liczbowa w sposób jawny, np. a = 1, A = 1, ą = 2, Ą = 2, … Rozwiązanie to wydaje się jednak mało eleganckie, a tworzenie pliku alfabetu niepotrzebnie czasochłonne.

Znacznie prościej jest utworzyć alfabet, w którym litery o kolejnych pozycjach będziemy oddzielać inaczej niż litery o tej samej pozycji, a program na tej podstawie sam przydzieli odpowiednie wartości poszczególnym literom. Na przykład w alfabecie aA ąĄ bB… litery nieoddzielone spacją zachowywałyby tę samą pozycję, natomiast spacja powodowałaby wzrost pozycji o 1. Można też na przykład litery mające tą samą pozycję oddzielać przecinkiem, a litery o kolejnych pozycjach – średnikiem: a,A;ą,Ą;b,B;c,C;ć,Ć;… Sygnałem kolejnej litery może być też oddzielająca spacja lub przecinek, a sygnałem kolejnej pozycji – nowa linia (zamiast średnika).

Schemat przykładowego algorytmu

Działanie programu nie może jak widać polegać na operacjach na wejściowym tekście. Algorytm musi wyglądać całkiem inaczej: kolejne rekordy zostają wczytane i ponumerowane, utworzone i ponumerowane zostają ich reprezentacje, a następnie to one muszą zostać posortowane. Program musi następnie utworzyć plik wynikowy, łącząc rekordy według zapamiętanych (starych) numerów reprezentacji.

Wbudowana w język programowania procedura wykona z tego wszystkiego prawdopodobnie tylko jedno zadanie: posortuje reprezentacje rekordów. Ponieważ jednak procedura ta ma w założeniu sortować leksykograficznie teksty, a nie ciągi liczb, może się zdarzyć, że jej działanie nie będzie poprawne, gdy na wejściu otrzyma cyfry zamiast liter. Jednak można przecież sekwencje liczb zamienić na sekwencje liter z alfabetu angielskiego – wówczas działanie programu sortującego na pewno będzie właściwe.

Zilustrujmy cały algorytm na przykładzie. Naszym zadaniem będzie alfabetyczne posortowanie pewnej listy wyrazów i wyrażeń, z uwzględnieniem spacji jaku znaku literowego o najniższym priorytecie.

1. Otwieramy plik wejściowy o następującej zawartości:

codzienny

po polsku

księżyc

polski

naprawdę

Polska

na pewno

Księżyc

Eleonora

co dzień

2. Wczytujemy zawartość każdej linii do tablicy: W[1] = "codzienny", W[2] = "po polsku", W[3] = "księżyc", itd.

3. Dla każdego rekordu tworzymy reprezentacje liczbowe, używając numerów ich miejsc w alfabecie (oczywiście program musi wcześniej wczytać ten alfabet i na tej podstawie przypisać odpowiednie liczby odpowiednim literom): R[1] = (4 20 6 33 12 7 18 18 32), R[2] = (22 20 0 22 20 15 25 14 28) – tu zero oznacza spację, R[3] = (14 25 12 8 35 32 4), itd. (zwróćmy uwagę, że R[3] i R[9] powinny być takie same).

4. Ponieważ liter w alfabecie jest mniej niż 100, dlatego wystarczy, jeśli wszystkie reprezentacje liczbowe będą dwucyfrowe. Do jednocyfrowych dopiszemy zera. Teraz R[1] = (04 20 06 33 12 07 18 18 32) itd.

5. Dla zapewnienia poprawności sortowania leksykograficznego zamieniamy każdą cyfrę literą alfabetu anglosaskiego tak, że 0 = a, 1 = b itd. aż do 9 = j. Ponieważ każdej literze oryginału będą odpowiadać teraz dwie kolejne litery, zbędne jest pozostawianie przerw, i zamiast ciągu liter czy par liter wygenerujemy od razu ciągi znakowe (słowa). Otrzymujemy tym sposobem kolejną tablicę: L[1] = "aecaagddbcahbibidc" (ten ciąg reprezentuje wyraz „codzienny”), L[2] = "cccaaacccabfcfbeci" (reprezentacja hasła „po polsku”), L[3] = "becfbcaidfdcae" (reprezentujące wyraz „Księżyc”) itd. Od tego momentu tablica R nie będzie nam więcej do niczego potrzebna. Musimy natomiast pamiętać zawartość tablic W i L.

6. Otrzymane bezsensowne zbitki liter poddajemy działaniu wbudowanej procedury sortującej; będzie ona działała poprawnie niezależnie od ustawień języka, strony kodowej itd.

7. Otrzymujemy tablicę tych samych słów, co tablica L, ale inaczej ponumerowanych. Dobrze, jeśli uda nam się stworzyć od razu tablicę pozycji, która nowej pozycji pozwoli przypisać stary indeks. Jeśli stosowany język programowania nie daje takiej możliwości, konieczna może okazać się w tym miejscu inwencja programisty, przerzucenie się na inny język programowania (PHP do tego celu nadaje się doskonale) albo też samodzielne napisanie dobrej procedury sortującej, zwracającej nie posortowaną tablicę słów, ale tablicę indeksów. W naszym wypadku P[1] = 6, co oznacza, że na pierwszej pozycji posortowanej tablicy znajdzie się L[6] (równe "aeca" i reprezentujące słowo „co”). Na podobnej zasadzie P[2] = 11, gdyż na drugim miejscu znajdzie się L[11] (równe "aecaaaagddbcahbj" i reprezentujące oryginalny rekord „co dzień”). Od tego momentu tablica L stanie się niepotrzebna.

8. Łączymy rekordy zapamiętane w tablicy W zgodnie z wartością elementów tablicy P. Ponieważ P[1] = 6, więc na pierwszą pozycję wstawiamy W[6] czyli "co", ponieważ P[2] = 11, na pozycji drugiej znajdzie się W[11] czyli "co dzień", ponieważ P[3] = 1, więc na pozycji trzeciej umieścimy "codzienny" itd. Takie postępowanie pozwoli nam odtworzyć bez zmian pierwotną strukturę rekordów pomimo faktu, że ich reprezentacje były tylko na tyle dokładne, ile było potrzeba do poprawnego posortowania tablicy (np. niwelowały różnicę między małymi a dużymi literami).

Jak widać z powyższego algorytmu, programistę czeka trochę pracy nawet wówczas, gdy korzysta z wbudowanych procedur sortujących. Rzadko kto mówi o tym na zajęciach z programowania…

Dwa poziomy sortowania

Przeanalizowany dopiero przed chwilą algorytm powinien nasunąć jeszcze jedną refleksję. Skoro bowiem przykłady księżyc i Księżyc mają dokładnie takie same reprezentacje, to czy ich kolejność w pliku wynikowym powinna być zupełnie przypadkowa? Być może jednak chcielibyśmy na przykład, aby wyraz pospolity księżyc wystąpił w słowniku przed nazwą własną Księżyc. Przykładów takich par różniących się tylko wielkością liter w całym leksykonie nie jest dużo, i możemy liczyć na to, że uda nam się je poprawić ręcznie. Jednak takie rozwiązanie jest dalekie od idealnego – komputery wymyślono po to, by to one wykonywały tego rodzaju żmudne poszukiwania, naszym zaś zadaniem jest jedynie napisanie stosownego programu.

Rozwiązanie istnieje i wcale nie jest takie trudne. Pamiętamy, że hasło księżyc zakodowaliśmy w postaci ciągu liczb (14 25 12 08 35 32 04), a następnie w postaci ciągu odpowiadających tym cyfrom liter "becfbcaidfdcae". Jeżeli teraz do tego ciągu dodamy drugi ciąg złożony wyłącznie z cyfr 0 i 1 lub od razu liter a i b odpowiadającym kolejnym literom hasła tak, że a występuje, jeśli litera hasła była mała, natomiast b jeśli duża, wówczas nasz ciąg ulegnie modyfikacji do następującej postaci liczbowej (14 25 12 08 35 32 04) (0 0 0 0 0 0 0) i literowej "becfbcaidfdcae aaaaaaa". Reprezentacja hasła Księżyc będzie się różnić jedną literą: "becfbcaidfdcae baaaaaa", i to zagwarantuje nam umieszczenie obu haseł we właściwej kolejności zarówno względem siebie, jak i względem reszty leksykonu.

Umówiliśmy się wyżej, że program będzie przypisywał pozycje poszczególnym literom alfabetu przy wczytywaniu pliku alfabetu. Ta sama procedura może jednocześnie każdej literze przypisać inną wartość, odpowiadającą dopiero co opisanemu drugiemu poziomowi sortowania. Jeśli litery o jednakowej pozycji w alfabecie umieszczone są w jednej linii, wówczas kolejnym literom w tej linii mogą być przypisywane kolejne wartości tak, że literze a przypiszemy pozycję główną 1 i pomocniczą 0, a literze A również pozycję główną 1, ale pomocniczą 1. Analogicznie litera ą uzyska pozycję główną 2 i pomocniczą 0, natomiast litera Ą pozycję główną 2 i pomocniczą 1.

Nasz program powinien na tym etapie poprawnie współpracować nie tylko z językiem polskim zakodowanym w ściśle określony sposób – pod warunkiem, że zachowamy możliwość wczytywania alfabetu z pliku zewnętrznego. Oczywiście dla języka polskiego i kodowania ISO Latin-2 musimy stworzyć inny alfabet niż dla języka polskiego i kodowania Windows-1250.

Sortowanie tekstów zawierających litery obce

W tekstach polskich mogą się zdarzyć wypadki wystąpienia liter obcych, takich jak é (w wyrazie attaché) lub Č (w nazwisku Čapek). Ponieważ mają one, co oczywiste, inne kodowanie niż zwykłe e czy C, powinny zostać dodane do alfabetu. Nie powinny jednak zajmować innych pozycji niż odpowiadające im litery bez znaków diakrytycznych – w polskich słownikach nie wyróżniamy bowiem specjalnej litery Č i przy porządkowaniu leksykonu „liczymy” ją jak zwykłe C. Chcielibyśmy jednak zapewne, aby wyrazy różniące się jedynie obecnością dodatkowego znaku diakrytycznego były także porządkowane, a nie pozostawione przypadkowi. Za naturalną kolejność na drugim poziomie sortowania – a więc w wypadku wyrazów różniących się tylko jedną literą – uznamy więc c C č Č. Wyrazy capek, Capek, Čapek, car znajdą się w leksykonie słownika w takiej właśnie kolejności (zakładając, że wszystkie one istnieją realnie).

Rozwiązanie polegające na tworzeniu alfabetu dwupoziomowego okazało się ponownie znacznie bardziej przydatne niż gdyby dwóm kolejnym literom przypisywać taką samą pozycję. Okazuje się bowiem, że czasami tę samą pozycję może zajmować nie tylko mała i duża litera alfabetu.

Sortowanie leksykonu w językach obcych

W języku polskim litery narodowe (ą, ć, ę, ł, ń, ó, ś, ź, ż) traktowane są tak samo jak pozostałe litery alfabetu. W niektórych językach obowiązują jednak inne zasady. Na przykład niemieckie litery ä, ö, ü dla celów leksykograficznych traktowane są tak samo jak zwykłe a, o, u. Tak samo traktowane są francuskie à, â, ä, ç, è, é, ê, ë, î, ï, ô, ö, ù, û, ü, ÿ, włoskie à, è, ì, ò, ù, hiszpańskie á, é, í, ó, ú, ū czy portugalskie à, á, â, ã, ç, é, ê, í, ò, ó, ô, õ, ú, ũ, ü. Jednocześnie kolejność haseł różniących się tylko rodzajem znaku diakrytycznego jest ustalona i zwykle zgodna z podaną tu kolejnością. Dlatego słowniki portugalskie podają np. o, ò, ó, oásis, …

Warto dokładnie zaznajomić się ze zwyczajami leksykografów dla danego języka, bo często nie wszystkie istniejące w tym języku litery z diakrytykami traktowane są jak litery bez takich znaków. Wyżej wspomnieliśmy już, że litera ę ma własne miejsce w alfabecie polskim, podczas gdy é (występujące w wyrazach obcych używanych w oryginalnej pisowni) nie ma osobnego miejsca i dla ustalenia porządku wyrazów w leksykonie jest liczona jak zwykłe e. W innych językach rozróżnienie takie wprowadzono także dla liter występujących w wyrazach rodzimych. I tak, w hiszpańskim litera ñ ma swoje własne miejsce w alfabecie, natomiast litery á, é, í, ó, ú, ū takiego miejsca nie mają. Poprawną kolejność alfabetyczną ilustruje następująca sekwencja: …, cantero, cántico, cantidad, cantimplora, cantina, canto, cantor, caña, cáñamo, cañería, … Widać z niej wyraźnie, że znak akcentu stawiany nad samogłoską nie wpływa na pozycję wyrazu w słowniku, natomiast znak tyldy postawiony nad literą n tworzy zupełnie nową literę.

W języku litewskim litery č, š, ž zajmują odrębne miejsca w alfabecie, podobnie jak ñ w hiszpańskim. Natomiast to samo miejsce zajmują litery oznaczające samogłoski i następujące modyfikacje tych liter: ą, ę, ė, į, ų, ū. Dodatkowo to samo miejsce w alfabecie jak litery i oraz į zajmuje litera y (fonetycznie oznaczająca w litewskim długie i) – mimo że nie jest przecież graficzną modyfikacją litery i. Jeżeli mamy ułożyć wyrazy różniące się tylko znakiem diakrytycznym, wówczas zawsze litery „czyste” a, e, i, u mają najwyższy priorytet, po nich następują litery z ogonkiem: ą, ę, į, ų, wreszcie ostatnie miejsce zajmują ė, y, ū. Poprawną kolejnością haseł w słowniku litewskim jest więc np. …, įbrukti, įcentrinis, ichtiologija, yda, įdagas, …

Sytuacja w języku litewskim jest nawet bardziej skomplikowana, gdyż hasła słownikowe noszą na ogół dodatkowe znaki oznaczające rodzaj intonacji (których nie stosuje się przy normalnym użyciu języka). Pozycję pierwszą w litewskim alfabecie zajmują więc: a, à, á, ã, ą, ą́, ą̃ (plus odpowiadające im duże litery). Podobnie na pozycji szóstej znajdą się e, è, é, ẽ, ę, ę́, ę̃, ė, ė́, ė͂ itd. (podana tu kolejność odpowiada rzeczywiście stosowanej kolejności sortowania drugiego poziomu). Znak tyldy oznaczający określony rodzaj intonacji umieszcza się także nad literami oznaczającymi spółgłoski płynne, tworząc nowe litery l͂, m̃, ñ, r̃.

We wszystkich takich wypadkach nie potrzeba modyfikować omówionego wyżej algorytmu, wystarczy jedynie poprawnie stworzony alfabet. Wykorzystujemy oczywiście drugi poziom sortowania, nie zapominając o dużych literach ze znakami diakrytycznymi, które powinny zawsze następować zaraz po małej literze z takim samym znakiem. Na przykład dla języka portugalskiego pierwszą pozycję w alfabecie zajmą a A à À á Á â Â ã Ã w takim właśnie porządku, wykorzystywanym dla drugiego poziomu sortowania.

Gdyby łączna liczba liter zajmujących taką samą pozycję przekroczyła 10 (tak na przykład będzie w słowniku litewskim ze znakami intonacji), do ich przedstawienia potrzeba będzie więcej niż jednej litery. Ponieważ reprezentacja potrzebna dla drugiego poziomu sortowania stanowi osobny wyraz, do reprezentacji możemy także wykorzystać cały alfabet angielski liczący 26 liter, co pozwoli co prawda ograniczyć się do reprezentacji jednoliterowych, ale wymagać będzie specjalnej procedury, odmiennej niż algorytm tworzenia reprezentacji hasła dla celów pierwszego poziomu sortowania.

Przypuśćmy, że w jakimś alfabecie przewidujemy pojawienie się następujących liter na pierwszej pozycji alfabetu: a A à À á Á â Â ã Ã ä Ä. Dla (fikcyjnych) wyrazów aba, àba, Ába, äba reprezentacje potrzebne do pierwszego poziomu sortowania będą wszystkie takie same: będzie to mianowicie ciąg liczbowy (01 02 01), przekształcany następnie na postać tekstową "abacab". Taka reprezentacja nie pozwoli jednak ułożyć haseł w odpowiedniej kolejności, dlatego konieczne stanie się dodanie drugiego ciągu, potrzebnego dla drugiego poziomu sortowania.

W ciągu tym literom a, b, c… przypiszemy kod liczbowy 00, literom A, B, C… – kod 01, literze à – kod 02, literze Á – kod 05, literze ä – kod 10. Hasło aba zostanie zatem zakodowane jako (01 02 01) (00 00 00), hasło àba jako (01 02 01) (02 00 00), hasło Ába jako (01 02 01) (05 00 00), wreszcie hasło äba jako (01 02 01) (10 00 00). Te same reprezentacje w postaci literowej wyglądać będą następująco: "abacab aaaaaa", "abacab acaaaa", "abacab afaaaa", "abacab baaaaa". Gdyby jednak użyć wszystkich liter angielskich do przedstawienia drugiego poziomu sortowania, wówczas reprezentacje wyglądałyby inaczej: "abacab aaa", "abacab caa", "abacab faa", "abacab kaa". Zauważmy, że niezależnie od przyjętej metody, hasła zostaną posortowane poprawnie (byle tylko stosować stale tę samą metodę dla wszystkich sortowanych haseł w danym sortowaniu).

Ligatury

Ortografia i zwyczaje leksykograficzne w niektórych językach są niekiedy tego rodzaju, że stosowany dotąd algorytm nie spełni swojej funkcji i będzie wymagać pewnych modyfikacji. Najprostszym tego typu wypadkiem są ligatury. Są to znaki złożone z dwóch połączonych ze sobą liter, które należy traktować tak, jakby rzeczywiście w ich miejscu występowały dwie litery. Najbardziej znane przykłady ligatur to francuskie æ, œ oraz niemieckie ß (które dodatkowo nie ma dużego odpowiednika).

Program po natrafieniu na ligaturę powinien zamienić ją nie na jeden, ale na dwa kody. W języku francuskim literze a przypiszemy (na pierwszym poziomie sortowania) kod liczbowy 01, literze e – kod 05, literze o – kod 15 (i kod literowy odpowiednio "ab", "af", "bf"). Ligatura æ powinna zatem zostać zakodowana jako 01 05 (literowo: "abaf"), zaś ligatura œ jako 15 05 (literowo: "bfaf"). Niemieckiej literze s przypiszemy kod 19 (literowo: "bj"), a zatem ligatura ß zakodowana zostanie jako 19 19 (czyli "bjbj"). Nie ma przy tym żadnego znaczenia, że historycznie jest to połączenie sz, a nie ss. Ważne, że w słownikach ß traktowane jest jak ss.

Do alfabetu należałoby więc dołączyć listę ligatur (w osobnym pliku) wraz z podaniem, jakiej kombinacji liter odpowiadają. Konieczne stanie się też określenie kodu używanego na drugim poziomie sortowania dla każdego ze składników ligatury (a przynajmniej dla pierwszego z tych składników). Nadanie wyższego kodu spowoduje, że hasła pisane z ligaturą zostaną umieszczone w słowniku po różniących się tylko tym, że nie użyto w nich ligatury. W alfabecie niemieckim przy pozycji 19 wystarczy przy tym podać s S ß. Dzięki osobno przekazanej informacji o istniejących ligaturach program będzie wiedział, żeby np. wyraz Ruß zakodować liczbowo jako (18 20 19 19) (1 0 2 0) i tekstowo jako "bicabjbj baca".

Należy dodatkowo mieć na uwadze, że nie każda litera będąca z pochodzenia ligaturą jest tak właśnie traktowana w leksykografii. Na przykład w alfabecie norweskim używa się litery æ, która jednak nie jest traktowana jako ligatura i ma swoje miejsce w alfabecie (końcowe litery alfabetu to z, æ, ø, å).

Dwuznaki

Dwuznakami nazywamy dwuliterowe połączenia, którym przypisuje się osobne miejsce w alfabecie. Z definicji tej wynika, że w języku polskim nie ma dwuznaków, a jedynie dwuliterowe połączenia o określonej wartości fonetycznej. Poprawną kolejnością w słowniku polskim będzie więc np. cały, chcieć, cichy, czoło.

Zupełnie inaczej jest (na ogół) w słownikach języka czeskiego, w których kombinację ch traktuje się tak, jakby stanowiła jedną literę, umieszczoną po h. Początek alfabetu czeskiego wygląda zatem następująco: a, b, c, č, d, e, f, g, h, ch, i, … (litery á, é, í itd. liczone są tak jak zwykłe a, e, i), a poprawną kolejnością wyrazów będzie cvičit, cyklista, čaj, čáp, čas, dál, estráda, film, gáz, had, hymna, chápat, chytrý, ihned. Kombinacja dž w języku czeskim nie jest natomiast traktowana jako dwuznak (tak samo jak dz, dź, dż w języku polskim), co jednak nie ma i tak żadnego znaczenia dla sortowania wyrazów z uwagi na pozycję ž na końcu alfabetu.

Dwuznaki występują, a przynajmniej mogą występować w alfabecie chorwackim. Jak pojedyncze litery traktuje się tu na ogół dž, dj (zapisywane zwykle specjalną literą đ), lj, nj. Na kolejnych pozycjach alfabetu chorwackiego znajdują się więc a, b, c, č, ć, d, dž, đ (dj), e, … W bardzo podobnie wyglądającym alfabecie słoweńskim (nieposiadającym tylko ć i đ) połączeń dž, lj, nj nie uważa się za dwuznaki.

W alfabecie albańskim za dwuznaki uważa się dh, gj, ll, nj, rr, sh, th, xh, zh (ponadto osobną literą jest ç).

W hiszpańskim za dwuznaki uważa się, lub przynajmniej uważano jeszcze niedawno, ch oraz ll. Pozycja ch w alfabecie jest jednak całkiem inna niż w czeskim, zupełnie inna jest też jego wartość fonetyczna. W portugalskim nie uważa się natomiast za dwuznaki połączeń ch, lh, nh.

W języku niderlandzkim, przynajmniej w wersji holenderskiej, występuje dwuznak ij, traktowany w alfabecie tak samo jak litera y. Dwa wyrazy różniące się tylko tym, że jeden pisany jest z użyciem y, a drugi z użyciem dwuznaku ij, zostałyby jednak ustawione w określonej kolejności – najpierw wyraz z y, potem z ij. W wersji flamandzkiej natomiast zdarza się traktowanie omawianej kombinacji jak zwykłego zbiegu dwóch liter, co całkowicie zmienia porządek leksykonu słownika flamandzkiego w porównaniu z holenderskim. Chcąc posortować listę haseł słownika niderlandzkiego musimy zatem ustalić, której z zasad będziemy się trzymać, i w zależności od tej decyzji wybrać odpowiedni słownik.

Oprócz alfabetu i listy ligatur będziemy musieli zatem dostarczyć do naszego programu także listę dwuznaków, którym będzie on przypisywał pojedynczą reprezentację. Nie wolno przy tym zapominać, że dwuznaki mogą być pisane bądź dwiema małymi literami, bądź pierwszą literą dużą (jeśli dwuznak znajduje się na początku nazwy pisanej od dużej litery). Na uwagę zasługuje zwyczaj pisania w holenderskim obu liter dwuznaku ij o tej samej wielkości, np. IJsselmeer, IJmuiden. Pamiętając o tym, że w istocie sortujemy nie wyrazy, ale ich liczbowe kody, do listy dwuznaków dopiszemy na wszelki wypadek nie dwie, ale trzy możliwości: ij, Ij, IJ. Tak samo w czeskim: ch, Ch, CH. Możliwościom tym nadamy odrębne kody potrzebne do drugiego poziomu sortowania.

Istnienie dwuznaków komplikuje algorytm stosowanego programu. Wiedząc, że język zawiera dwuznaki, można by przy tworzeniu reprezentacji liczbowej (tablicy R) wczytywać po dwie litery wyrazu (o ile to możliwe) i sprawdzać, czy przypadkiem nie stanowią one dwuznaku. Jeśli stanowią, do reprezentacji powinna być dodana jedna liczba, a kolejna analiza powinna objąć dwie kolejne litery następujące po dwuznaku. Jeśli jednak dwie wczytane litery dwuznaku nie stanowią, tylko pierwsza powinna zostać zamieniona na reprezentację. Następnie należy analizować osobno literę drugą i kolejną literę wyrazu.

Pokażemy tę procedurę na przykładzie. Przypuśćmy, że sortujemy czeski leksykon zawierający wyraz scházet. Najpierw wczytujemy dwie litery: sc. Nie stanowią one dwuznaku, pierwszej z nich przypisujemy więc stosowną reprezentację. Błędem byłoby w tym momencie przypisanie reprezentacji drugiej literze. Zamiast tego wczytujemy litery drugą i trzecią: ch. Ponieważ stanowią one dwuznak, przypisujemy obu pojedynczą reprezentację. Nie wczytujemy tym razem trzeciej i czwartej litery, bowiem trzecia stanowiła część dwuznaku. Zamiast tego od razu wczytujemy litery czwartą i piątą, itd. Program musi też zareagować adekwatnie, dochodząc do końca wyrazu, gdy pozostanie tylko jedna litera.

Alfabety

Litery podanych poniżej alfabetów oddzielono przecinkami i spacjami; dla uproszczenia nie podano w ogóle dużych liter. W każdym alfabecie umieszczono komplet liter anglosaskich, łącznie z używanymi tylko do zapisu wyrazów obcych o nieprzyswojonej pisowni. W nawiasie po danej literze wypisano wszystkie jej modyfikacje mające ten sam priorytet na pierwszym poziomie sortowania. Uwzględniono znaki intonacji używane tylko w tekstach szkolnych i naukowych (są one bowiem stosowane w każdym dobrym słowniku). Kolejność tych modyfikacji ma znaczenie na drugim poziomie sortowania. Po średniku podano ligatury wraz z informacją, jak należy je traktować przy ustalaniu kolejności wyrazów.

Albański

a (á, â), b, c, ç, d, dh, e (é, ê), ë (ë́), f, g, gj, h, i (í, î), j, k, l, ll, m, n, nj, o (ó), p, q, r, rr, s, sh, t, th, u (ú, û), v, w, x, xh, y (ý, ŷ), z, zh

Liter samogłoskowych ze znakami akutu używa się tylko w słownikach dla zaznaczenia miejsca akcentu. Litery ze znakiem cyrkumfleksu są używane w tekstach dialektalnych (gegijskich).

Angielski

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

Chorwacki

a (à, ȁ, á, ȃ, ā), b, c, č, ć, d, dž, đ (dj), e (è, ȅ, é, ȇ, ē), f, g, h, i (ì, ȉ, í, ȋ, ī), j, k, l, lj, m, n, nj, o (ò, ȍ, ó, ȏ, ō), p, q, r (r̀, ȑ, ŕ, ȓ, r̄), s, š, t, u (ù, ȕ, ú, ȗ, ū), v, w, x, y, z, ž

Liter samogłoskowych ze znakami intonacji i długości używa się tylko w słownikach i podręcznikach.

Czeski

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, ž

Duński

a, b, c, d, e (é), f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, æ, ø, å

Francuski

a (à, â, ä), b, c (ç), d, e (è, é, ê, ë), f, g, h, i (î, ï), j, k, l, m, n, o (ô, ö), p, q, r, s, t, u (ù, û, ü), v, w, x, y (ÿ), z; æ = ae, œ = oe

Hiszpański

a (á), b, c, ch, d, e (é), f, g, h, i (í), j, k, l, ll, m, n, ñ, o (ó), p, q, r, s, t, u (ú, ū), v, w, x, y, z

W nowszych źródłach nie ma dwuznaków ch, ll – taktuje się je jak zwykłe zbitki liter.

Litewski

Litewskie znaki intonacji nie zostały uwzględnione w fontach standardowych. Aby oddać poprawną postać używanych symboli, opracowane zostały fonty specjalne. Poprawne wyświetlenie poniższego alfabetu wymaga zainstalowania darmowego fontu Palemonas.

a (à, á, ã, ą, , ), b, c, č, d, e (è, é, ẽ, ę, , , ė, , ), f, g, h, i (, , , į, , , y, ý, ỹ), j, k, l (), m (), n (ñ), o (ò, ó, õ), p, q, r (), s, š, t, u (ù, ú, ũ, ų, , , ū, , ), v, w, x, z, ž

Użycie standardowego fontu unikodowego wymaga tworzenia znaków złożonych, z których nie wszystkie wyświetlane są poprawnie:

a (à, á, ã, ą, ą́, ą̃), b, c, č, d, e (è, é, ẽ, ę, ę́, ę̃, ė, ė́, ė͂), f, g, h, i (ì, í, ĩ, į, į́, į͂, y, ý, ỹ), j, k, l (l͂), m (m̃), n (ñ), o (ò, ó, õ), p, q, r (r̃), s, š, t, u (ù, ú, ũ, ų, ų́, ų̃, ū, ū́, ū͂), v, w, x, z, ž

Niderlandzki

a, b, c, d, e (ë), f, g, h, i (ï), j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y (ij), z; ij = y

Niemiecki

a (ä), b, c, d, e, f, g, h, i, j, k, l, m, n, o (ö), p, q, r, s, t, u (ü), v, w, x, y, z; ß = ss

Norweski

a, b, c, d, e (é), f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, æ, ø, å

Polski

a, ą, b, c, ć, d, e, ę, f, g, h, i, j, k, l, ł, m, n, ń, o, ó, p, q, r, s, ś, t, u, v, w, x, y, z, ź, ż

Portugalski

a (à, á, â, ã), b, c (ç), d, e (é, ê), f, g, h, i (í), j, k, l, m, n, o (ò, ó, ô, õ), p, q, r, s, t, u (ú, ũ, ü), v, w, x, y, z

Rumuński

a, ă, â, b, c, d, e, f, g, h, i, î, j, k, l, m, n, o, p, q, r, s, ş, t, ţ, u, v, w, x, y, z

Słowacki

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, ž

Słoweński

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

Szwedzki

a, b, c, d, e (é), f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, å, ä, ö

Zamiast znaku umlautu w literach ä, ö zdarza się użycie tyldy: ã, õ.

Turecki

a (â), b, c, ç, d, e, f, g, ğ, h, i (î), ı, j, k, l, m, n, o, ö, p, q, r, s, ş, t, u, ü, v, w, x, y, z

Włoski

a (à), b, c, d, e (è, é), f, g, h, i (ì), j, k, l, m, n, o (ò, ó), p, q, r, s, t, u (ù), v, w, x, y, z

Artykuł został opublikowany także na witrynie autora pod adresem http://grzegorj.5v.pl/lingwpl/lekssort.html

nauka