Sortowanie - Collation

Sortowanie to zestawienie pisemnych informacji w standardowe zamówienie. Wiele systemów sortowania opiera się na porządku numerycznym lub alfabetycznym lub ich rozszerzeniach i kombinacjach. Sortowanie jest podstawowym elementem większości biurowych systemów archiwizacji , katalogów bibliotecznych i leksykonów .

Sortowanie różni się od klasyfikacji tym, że same klasy niekoniecznie są uporządkowane. Jednak nawet jeśli kolejność klas jest nieistotna, identyfikatory klas mogą należeć do uporządkowanego zestawu, umożliwiając algorytmowi sortowania uporządkowanie elementów według klas.

Formalnie rzecz biorąc, metoda sortowania zazwyczaj definiuje całkowitą kolejność w zbiorze możliwych identyfikatorów, zwanych kluczami sortowania, co w konsekwencji daje całkowitą kolejność wstępną zbioru informacji (elementy o tym samym identyfikatorze nie są umieszczane w żadnej określonej kolejności).

Algorytm porównywania, taki jak algorytm porównywania Unicode, definiuje kolejność poprzez proces porównywania dwóch podanych ciągów znaków i decydowania, który powinien pojawić się przed drugim. Gdy kolejność została zdefiniowana w ten sposób, algorytm sortowania może być użyty do umieszczenia listy dowolnej liczby pozycji w tej kolejności.

Główną zaletą sortowania jest to, że umożliwia użytkownikowi szybkie i łatwe odnalezienie elementu na liście lub potwierdzenie, że nie ma go na liście. W systemach automatycznych można to zrobić za pomocą algorytmu wyszukiwania binarnego lub wyszukiwania interpolacyjnego ; wyszukiwanie ręczne można przeprowadzić przy użyciu mniej więcej podobnej procedury, chociaż często jest to wykonywane nieświadomie. Inne zalety to możliwość łatwego odnalezienia pierwszego lub ostatniego elementu na liście (najprawdopodobniej przydatne w przypadku danych posortowanych numerycznie) lub elementów z danego zakresu (przydatne ponownie w przypadku danych liczbowych, a także przy dane uporządkowane alfabetycznie, gdy można być pewnym tylko kilku pierwszych liter poszukiwanej pozycji lub pozycji).

Zamawianie

Numeryczne i chronologiczne

Ciągi reprezentujące liczby mogą być sortowane na podstawie wartości liczb, które reprezentują. Na przykład „-4”, „2,5”, „10”, „89”, „30 000”. Należy zauważyć, że zwykłe zastosowanie tej metody może zapewnić tylko częściowe uporządkowanie w ciągach, ponieważ różne ciągi mogą reprezentować tę samą liczbę (jak w przypadku „2” i „2.0” lub, gdy używana jest notacja naukowa , „2e3” i „2000” ).

Podobne podejście można zastosować z ciągami reprezentującymi daty lub inne elementy, które można uporządkować chronologicznie lub w inny naturalny sposób.

Alfabetyczny

Kolejność alfabetyczna jest podstawą dla wielu systemów sortowania gdzie elementy informacji są identyfikowane przez ciągów składających się głównie z liter z alfabetu . Kolejność ciągów opiera się na istnieniu standardowej kolejności dla liter danego alfabetu. (System nie ogranicza się do alfabetów w ścisłym sensie technicznym; języki używające sylabariusza lub abugidy , na przykład Cherokee , mogą używać tej samej zasady porządkowania, pod warunkiem, że istnieje ustalona kolejność używanych symboli.)

Aby zdecydować, który z dwóch ciągów jest pierwszy w kolejności alfabetycznej, najpierw porównywane są ich pierwsze litery. Ciąg, którego pierwsza litera pojawia się wcześniej w alfabecie, znajduje się na pierwszym miejscu w kolejności alfabetycznej. Jeśli pierwsze litery są takie same, porównuje się drugie litery i tak dalej, aż do ustalenia kolejności. (Jeśli w jednym ciągu skończą się litery do porównania, uważa się, że jest on pierwszy; na przykład „koszyk” znajduje się przed „kozioł”.) Wynikiem ułożenia zestawu ciągów w kolejności alfabetycznej jest to, że słowa z tym samym pierwszym litery są zgrupowane razem, aw ramach takiej grupy słowa z tymi samymi dwoma pierwszymi literami są zgrupowane razem i tak dalej.

Wielkie litery są zwykle traktowane jako odpowiedniki odpowiadających im małych liter. (Aby zapoznać się z alternatywnymi zabiegami w systemach komputerowych, patrz Automatyczne sortowanie poniżej.)

W przypadku korzystania z kolejności alfabetycznej mogą obowiązywać pewne ograniczenia, komplikacje i specjalne konwencje:

  • Gdy łańcuchy zawierają spacje lub inne dzielniki wyrazów, należy podjąć decyzję, czy zignorować te dzielniki, czy też traktować je jako symbole poprzedzające wszystkie inne litery alfabetu. Na przykład, jeśli przyjmie się pierwsze podejście, to „parking” pojawi się po „węgiel” i „karpie” (tak jakby było napisane „parking”), podczas gdy w drugim podejściu „parking” będzie przed tymi dwa słowa. Pierwsza reguła jest używana w wielu (ale nie we wszystkich) słownikach , druga w książkach telefonicznych (tak, że Wilson, Jim K pojawia się z innymi osobami o imieniu Wilson, Jim, a nie po Wilson, Jimbo).
  • Skróty mogą być traktowane tak, jakby zostały podane w całości. Na przykład imiona zawierające „św.”. (skrót od angielskiego słowa Saint ) są często uporządkowane tak, jakby były napisane jako „Saint”. Istnieje również tradycyjna konwencja w języku angielskim, że nazwiska zaczynające się od Mc i M' są wymienione tak, jakby te przedrostki były napisane Mac .
  • Ciągi reprezentujące imiona i nazwiska często są wymienione w kolejności alfabetycznej nazwisk, nawet jeśli imię jest pierwsze. Na przykład Juan Hernandes i Brian O'Leary powinni zostać posortowani jako „Hernandes, Juan” i „O'Leary, Brian”, nawet jeśli nie są napisane w ten sposób.
  • Bardzo popularne początkowe słowa, takie jak The w języku angielskim, są często ignorowane do celów sortowania. Więc Lśnienie będzie po prostu posortowane jako "Lśnienie" lub "Lśnienie, The".
  • Gdy niektóre ciągi zawierają cyfry (lub inne znaki nieliterowe), możliwe są różne podejścia. Czasami takie znaki są traktowane tak, jakby pojawiły się przed lub po wszystkich literach alfabetu. Inną metodą jest sortowanie liczb alfabetycznie tak, jak byłyby pisane: na przykład 1776 zostałoby posortowane tak, jakby pisane było „siedemnaście siedemdziesiąt sześć”, a 24 heures du Mans, jakby pisane „vingt-quatre…” (w języku francuskim). za „dwadzieścia cztery”). Kiedy cyfry lub inne symbole są używane jako specjalne graficzne formy liter, jak w 1337 dla leet lub Se7en dla tytułu filmu Seven , mogą być one sortowane tak, jakby były tymi literami.
  • Języki mają różne konwencje traktowania zmodyfikowanych liter i niektórych kombinacji liter. Na przykład, w hiszpańskim litery ń jest traktowany jako podstawowy litery następującym n oraz digrafów ch i II były poprzednio (do 1994) traktowano jako podstawowe kolejnych liter C oraz L , chociaż obecnie alfabetycznie jako kombinacje dwu liter. Listę takich konwencji dla różnych języków można znaleźć w kolejności alfabetycznej § Konwencje językowe .

W kilku językach zasady zmieniły się z biegiem czasu, więc starsze słowniki mogą używać innej kolejności niż współczesne. Ponadto sortowanie może zależeć od użycia. Na przykład niemieckie słowniki i książki telefoniczne stosują różne podejścia.

Sortowanie radykalne i udarowe

Zobacz także indeksowanie chińskich znaków

Inną formą sortowania jest radykalna i-suwowy sortowania , używane do nieliterowymi systemów piśmienniczych takich jak hanzi z chińskim a kanji z japońskim , którego tysiące symboli przeciwstawić zamawianie przez konwencję. W tym systemie identyfikowane są wspólne składniki znaków; są to tak zwane rodniki w języku chińskim i systemy logoograficzne wywodzące się z języka chińskiego. Znaki są następnie pogrupowane według ich podstawowego rodnika, a następnie uporządkowane według liczby pociągnięć pióra w ramach rodników. Gdy nie ma żadnego oczywistego radykału lub więcej niż jeden radykał, obowiązuje konwencja, która jest używana do zestawienia. Na przykład chiński znak 妈 (oznaczający „matka”) jest sortowany jako znak sześciocyfrowy pod trzycyfrowym pierwiastkiem pierwotnym 女.

System radykalny i udarowy jest nieporęczny w porównaniu z systemem alfabetycznym, w którym jest kilka znaków, wszystkie są jednoznaczne. Wybór, które elementy logografu składają się z oddzielnych rodników, a który z nich jest pierwotny, nie jest jednoznaczny. W rezultacie języki logograficzne często uzupełniają porządkowanie radykalne i kreskowe o alfabetyczne sortowanie fonetycznej konwersji logografów. Na przykład słowo kanji Tōkyō (東京) można posortować tak, jakby było zapisane japońskimi znakami sylabariusza hiragana jako „to-u-ki- yo -u ” (とうきょう), używając konwencjonalnej kolejności sortowania dla tych postacie.

Ponadto, w Wielkich Chinach, w niektórych oficjalnych dokumentach nakaz wykreślania nazwisk jest konwencją, w której nazwiska osób są wymieniane bez hierarchii.

System radykalny-i-skok lub jakaś podobna metoda dopasowywania wzorców i liczenia kresek była tradycyjnie jedyną praktyczną metodą konstruowania słowników, której można było użyć do wyszukania logografu, którego wymowa była nieznana. Wraz z pojawieniem się komputerów dostępne są teraz programy słownikowe, które umożliwiają ręczne pisanie znaków za pomocą myszy lub rysika.

Automatyzacja

Gdy informacje są przechowywane w systemach cyfrowych, sortowanie może stać się procesem zautomatyzowanym. Niezbędne jest wówczas zaimplementowanie odpowiedniego algorytmu sortowania , który pozwoli na sortowanie informacji w sposób zadowalający dla danej aplikacji. Często celem będzie osiągnięcie porządku alfabetycznego lub numerycznego zgodnego ze standardowymi kryteriami opisanymi w poprzednich sekcjach. Jednak nie wszystkie z tych kryteriów są łatwe do zautomatyzowania.

Najprostszy rodzaj automatycznego sortowania opiera się na kodach numerycznych symboli w zestawie znaków , takich jak kodowanie ASCII (lub dowolny z jego nadzbiorów, takich jak Unicode ), przy czym symbole są uporządkowane w rosnącej kolejności numerycznej ich kodów, a to rozciągnięcie porządkowania na ciągi znaków zgodnie z podstawowymi zasadami porządkowania alfabetycznego (mówiąc matematycznie porządkowanie leksykograficzne ). Tak więc program komputerowy może traktować znaki a , b , C , d i $ jako uporządkowane $ , C , a , b , d (odpowiednie kody ASCII to $ = 36, a = 97, b = 98, C = 67 id = 100). Dlatego ciągi zaczynające się od C , M lub Z byłyby sortowane przed ciągami z małymi literami a , b , itd. Jest to czasami nazywane porządkiem ASCIIbetical . Odbiega to od standardowej kolejności alfabetycznej, szczególnie ze względu na kolejność wielkich liter przed wszystkimi małymi (i ewentualnie sposób traktowania spacji i innych znaków nieliterowych). Dlatego jest często stosowany z pewnymi zmianami, najbardziej oczywistą jest konwersja wielkości liter (często na wielkie, ze względów historycznych) przed porównaniem wartości ASCII.

W wielu algorytmach porównywania porównywanie opiera się nie na numerycznych kodach znaków, ale w odniesieniu do kolejności porównywania – kolejności, w której znaki mają przychodzić w celu porównywania – oraz innych zasad porządkowania właściwych dla daną aplikację. Może to służyć do zastosowania poprawnych konwencji używanych do porządkowania alfabetycznego w danym języku, właściwego postępowania z literami o różnej wielkości, zmodyfikowanymi literami , dwuznacznikami , określonymi skrótami itd., jak wspomniano powyżej w części Porządek alfabetyczny , a szczegółowo w części Alfabetycznie zamów artykuł. Takie algorytmy są potencjalnie dość złożone i mogą wymagać kilku przejść przez tekst.

Problemy są jednak nadal powszechne, gdy algorytm musi obejmować więcej niż jeden język. Na przykład w niemieckich słowników słowo ökonomisch pochodzi między offenbar i olfaktorisch , natomiast turecki słowniki traktują o i ö jako różnych liter, składających oyun przed öbür .

Standardowym algorytmem sortowania dowolnej kolekcji ciągów składających się z dowolnych standardowych symboli Unicode jest algorytm sortowania Unicode . Można to dostosować do użycia odpowiedniej kolejności sortowania dla danego języka, dostosowując jego domyślną tabelę sortowania. Kilka takich dostosowań jest gromadzonych w repozytorium danych Common Locale Data Repository .

Sortuj klucze

W niektórych aplikacjach ciągi, według których są sortowane elementy, mogą różnić się od wyświetlanych identyfikatorów. Na przykład Lśnienie może być posortowane jako Lśnienie (patrz kolejność alfabetyczna powyżej), ale nadal może być pożądane wyświetlanie go jako Lśnienie . W takim przypadku można przechowywać dwa zestawy ciągów, jeden do celów wyświetlania, a drugi do porównywania. Łańcuchy używane do sortowania w ten sposób nazywane są kluczami sortowania .

Problemy z liczbami

Czasami pożądane jest uporządkowanie tekstu z osadzonymi liczbami w odpowiedniej kolejności numerycznej. Na przykład „Rysunek 7b” występuje przed „Rysunek 11a”, mimo że „7” występuje po „1” w Unicode . Można to rozszerzyć na cyfry rzymskie . Takie zachowanie nie jest szczególnie trudne do wygenerowania, o ile sortowane są tylko liczby całkowite, chociaż może znacznie spowolnić sortowanie. Na przykład Microsoft Windows robi to podczas sortowania nazw plików .

Właściwe sortowanie miejsc dziesiętnych jest nieco trudniejsze, ponieważ różne lokalizacje używają różnych symboli dla kropki dziesiętnej , a czasami ten sam znak używany jako kropka dziesiętna jest również używany jako separator, na przykład „Sekcja 3.2.5”. Nie ma uniwersalnej odpowiedzi na pytanie, jak sortować takie ciągi; wszelkie reguły są zależne od aplikacji.

Rosnąca kolejność liczb różni się od kolejności alfabetycznej, np. 11 jest alfabetycznie przed 2. Można to ustalić z zerami wiodącymi : 02 jest alfabetycznie przed 11. Patrz np. ISO 8601 .

Również −13 pojawia się alfabetycznie po −12, chociaż jest mniej. W przypadku liczb ujemnych, aby kolejność rosnąco odpowiadała sortowaniu alfabetycznemu, potrzebne są bardziej drastyczne środki, takie jak dodanie stałej do wszystkich liczb, aby wszystkie były dodatnie.

Etykietowanie zamówionych pozycji

W niektórych kontekstach cyfry i litery są wykorzystywane nie tyle jako podstawa do składania zamówienia, ale jako sposób oznaczania już zamówionych przedmiotów. Na przykład strony, sekcje, rozdziały i tym podobne, a także pozycje list są często „ponumerowane” w ten sposób. Serie oznakowania, które można zastosować, obejmują zwykłe cyfry arabskie (1, 2, 3, ...), cyfry rzymskie (I, II, III, ... lub i, ii, iii, ...) lub litery (A , B, C, ... lub a, b, c, ...). (Alternatywną metodą wskazywania elementów listy, bez ich numerowania, jest użycie listy punktowanej .)

Gdy do wyliczenia używane są litery alfabetu , istnieją pewne konwencje specyficzne dla języka określające, które litery są używane. Na przykład pominięto rosyjskie litery Ъ i Ь (które na piśmie służą tylko do zmiany poprzedzającej spółgłoski ), a zwykle także Ы , Й i Ё . Również w wielu językach, które używają rozszerzonego pisma łacińskiego , zmodyfikowane litery często nie są używane w wyliczeniach.

Zobacz też

Uwagi

Bibliografia

Linki zewnętrzne