Die Sortierung bezeichnet die Zusammenstellung schriftlicher Informationen in einer standardisierten Reihenfolge. Viele Sortiersysteme basieren auf numerischer oder alphabetischer Ordnung oder deren Erweiterungen und Kombinationen. Die Sortierung ist ein grundlegendes Element der meisten Büroablagesysteme , Bibliothekskataloge und Nachschlagewerke .

Die Kollation unterscheidet sich von der Klassifizierung dadurch, dass die Klassen selbst nicht notwendigerweise geordnet sind. Selbst wenn die Reihenfolge der Klassen irrelevant ist, können die Klassenbezeichner Elemente einer geordneten Menge sein, sodass ein Sortieralgorithmus die Elemente nach Klasse anordnen kann.

Formal betrachtet definiert eine Sortiermethode typischerweise eine totale Ordnung über eine Menge möglicher Identifikatoren, sogenannte Sortierschlüssel, die folglich eine totale Vorordnung über die Menge der Informationselemente erzeugt (Elemente mit demselben Identifikator werden in keiner definierten Reihenfolge angeordnet).

Ein Sortieralgorithmus wie der Unicode-Sortierungsalgorithmus definiert eine Reihenfolge, indem er zwei gegebene Zeichenketten vergleicht und entscheidet, welche vor der anderen stehen soll. Sobald eine Reihenfolge definiert ist, kann ein Sortieralgorithmus verwendet werden, um eine Liste mit beliebig vielen Elementen in diese Reihenfolge zu bringen.

Der Hauptvorteil der Sortierung liegt darin, dass Benutzer schnell und einfach ein Element in einer Liste finden oder dessen Fehlen bestätigen können. In automatischen Systemen geschieht dies mittels binärer Suche oder Interpolation ; die manuelle Suche kann mit einem ähnlichen Verfahren durchgeführt werden, allerdings oft unbewusst. Weitere Vorteile sind das einfache Auffinden des ersten oder letzten Elements (besonders nützlich bei numerisch sortierten Daten) oder von Elementen in einem bestimmten Bereich (ebenfalls nützlich bei numerischen Daten und auch bei alphabetisch sortierten Daten, wenn man sich nur der ersten Buchstaben des gesuchten Elements oder der gesuchten Elemente sicher ist).

Bestellung

Numerisch und chronologisch

Zeichenketten, die Zahlen repräsentieren , können anhand der Werte der von ihnen dargestellten Zahlen sortiert werden. Beispiele hierfür sind „−4“, „2,5“, „10“, „89“ und „30.000“. Die reine Anwendung dieser Methode liefert jedoch nur eine Teilsortierung der Zeichenketten, da verschiedene Zeichenketten dieselbe Zahl darstellen können (wie etwa „2“ und „2,0“ oder, in wissenschaftlicher Notation , „2e3“ und „2000“).

Ein ähnlicher Ansatz kann bei Zeichenketten verfolgt werden, die Datumsangaben oder andere Elemente darstellen, die chronologisch oder auf andere natürliche Weise geordnet werden können.

Alphabetisch

Die alphabetische Reihenfolge bildet die Grundlage vieler Sortiersysteme, in denen Informationen durch Zeichenketten identifiziert werden, die hauptsächlich aus Buchstaben eines Alphabets bestehen . Die Reihenfolge dieser Zeichenketten setzt eine festgelegte Reihenfolge der Buchstaben des jeweiligen Alphabets voraus. (Das System ist nicht auf Alphabete im engeren technischen Sinne beschränkt; Sprachen, die eine Silbenschrift oder Abugida verwenden , wie beispielsweise Cherokee , können dasselbe Ordnungsprinzip anwenden, sofern eine festgelegte Reihenfolge für die verwendeten Symbole existiert.)

Um zu entscheiden, welche von zwei Zeichenketten alphabetisch an erster Stelle steht, werden zunächst ihre Anfangsbuchstaben verglichen. Die Zeichenkette, deren Anfangsbuchstabe im Alphabet weiter vorne steht, wird zuerst geordnet. Sind die Anfangsbuchstaben gleich, werden die zweiten Buchstaben verglichen usw., bis die Reihenfolge feststeht. (Wenn eine Zeichenkette keine Buchstaben mehr zum Vergleichen hat, gilt sie als erste; beispielsweise steht „cart“ vor „carthorse“.) Das Ergebnis der alphabetischen Sortierung von Zeichenketten ist, dass Wörter mit demselben Anfangsbuchstaben gruppiert werden, und innerhalb einer solchen Gruppe werden Wörter mit denselben ersten beiden Buchstaben gruppiert usw.

Großbuchstaben werden üblicherweise den entsprechenden Kleinbuchstaben gleichgestellt. (Für alternative Vorgehensweisen in computergestützten Systemen siehe „Automatisierte Sortierung“ weiter unten.)

Bei Verwendung der alphabetischen Reihenfolge können bestimmte Einschränkungen, Komplikationen und besondere Konventionen gelten:

  • Wenn Zeichenketten Leerzeichen oder andere Worttrennzeichen enthalten, muss entschieden werden, ob diese Trennzeichen ignoriert oder als Vorzeichen vor allen anderen Buchstaben des Alphabets behandelt werden. Beispielsweise würde bei der ersten Variante „car park“ nach „carbon“ und „carp“ stehen (genau wie bei der Schreibweise „carpark“), während es bei der zweiten Variante vor diesen beiden Wörtern stünde. Die erste Regel wird in vielen (aber nicht allen) Wörterbüchern verwendet , die zweite in Telefonbüchern (sodass Wilson, Jim K. zusammen mit anderen Personen namens Wilson, Jim und nicht nach Wilson, Jimbo erscheint).
  • Abkürzungen können so behandelt werden, als wären sie ausgeschrieben. Beispielsweise werden Namen mit „St.“ (Kurzform des englischen Wortes Saint ) oft so geführt, als würden sie „Saint“ geschrieben. Im Englischen gibt es außerdem die traditionelle Konvention, Nachnamen, die mit Mc oder M' beginnen, so aufzulisten, als würden diese Präfixe Mac geschrieben .
  • Zeichenketten, die Personennamen repräsentieren, werden oft alphabetisch nach Nachnamen sortiert, selbst wenn der Vorname an erster Stelle steht. Beispielsweise sollten Juan Hernandes und Brian O'Leary als „Hernandes, Juan“ und „O'Leary, Brian“ sortiert werden, auch wenn sie nicht so geschrieben werden.
  • Sehr häufige Anfangswörter, wie zum Beispiel „The“ im Englischen, werden bei der Sortierung oft ignoriert. So würde „The Shining “ entweder nur als „Shining“ oder als „Shining, The“ sortiert werden.
  • Wenn einige der Zeichenketten Ziffern (oder andere Sonderzeichen) enthalten, sind verschiedene Vorgehensweisen möglich. Manchmal werden solche Zeichen so behandelt, als stünden sie vor oder nach allen Buchstaben des Alphabets. Eine andere Methode besteht darin, Zahlen alphabetisch so zu sortieren, wie sie geschrieben würden: zum Beispiel würde 1776 wie „siebzehn sechsundsiebzig“ und 24 heures du Mans wie „vingt-quatre…“ (französisch für „vierundzwanzig“) sortiert. Werden Ziffern oder andere Symbole als spezielle grafische Formen von Buchstaben verwendet, wie etwa 1337 für „leet“ oder „Se7en“ für den Filmtitel „Sieben“ , können sie so sortiert werden, als wären sie diese Buchstaben.
  • Sprachen haben unterschiedliche Konventionen für die Behandlung von modifizierten Buchstaben und bestimmten Buchstabenkombinationen. Im Spanischen beispielsweise wird der Buchstabe ñ nach n als Basisbuchstabe behandelt , und die Digraphen ch und ll wurden früher (bis 1994) nach c und l als Basisbuchstaben behandelt , obwohl sie heute alphabetisch als Zwei-Buchstaben-Kombinationen geführt werden. Eine Liste solcher Konventionen für verschiedene Sprachen finden Sie unter Alphabetische Reihenfolge § Sprachspezifische Konventionen .

In vielen Sprachen haben sich die Regeln im Laufe der Zeit geändert, daher verwenden ältere Wörterbücher möglicherweise eine andere Sortierung als moderne. Darüber hinaus kann die Sortierung vom jeweiligen Verwendungszweck abhängen. Beispielsweise verwenden deutsche Wörterbücher und Telefonbücher unterschiedliche Ansätze.

Wurzelsortierung

Einige arabische Wörterbücher, wie beispielsweise das zweisprachige A Dictionary of Modern Written Arabic von Hans Wehr , gruppieren und sortieren arabische Wörter nach semitischer Wurzel . [ 1 ] Beispielsweise sind die Wörter kitāba ( كتابة „Schreiben“), kitāb ( كتاب „Buch“), kātib ( كاتب „Schriftsteller“), maktaba ( مكتبة „Bibliothek“), maktab ( مكتب „Büro“), maktūb ( مكتوب „Schicksal“ oder „geschrieben“) zusammengefasst triliterale Wurzel k - t - b ( ك ت ب ), die „Schreiben“ bedeutet. [ 2 ]

Radikal- und Strichsortierung

Eine weitere Form der Sortierung ist die Radikal-Strich-Sortierung , die bei nicht-alphabetischen Schriftsystemen wie den Hanzi des Chinesischen und den Kanji des Japanischen Anwendung findet , deren Tausende von Symbolen sich einer konventionellen Ordnung entziehen. In diesem System werden die gemeinsamen Bestandteile der Zeichen identifiziert; diese werden im Chinesischen und in von China abgeleiteten logografischen Systemen Radikale genannt . Die Zeichen werden dann nach ihrem Hauptradikal gruppiert und anschließend nach der Anzahl der Striche innerhalb der Radikale geordnet. Gibt es kein eindeutiges Radikal oder mehrere, bestimmt die Konvention, welches Radikal für die Sortierung verwendet wird. Beispielsweise wird das chinesische Zeichen 妈 (Bedeutung: „Mutter“) als sechsstrichiges Zeichen unter dem dreistrichigen Hauptradikal 女 (Bedeutung: „Frau“) sortiert.

Das Radikal-Strich-System ist im Vergleich zu einem alphabetischen System mit wenigen, eindeutigen Zeichen umständlich. Die Zuordnung der Bestandteile eines Logogramms zu separaten Radikalen und die Bestimmung des primären Radikals sind nicht eindeutig. Daher ergänzen logographische Sprachen die Radikal-Strich-Reihenfolge oft durch eine alphabetische Sortierung der phonetischen Umwandlung der Logogramme. Beispielsweise kann das Kanji-Wort Tōkyō (東京) so sortiert werden, als wäre es in den japanischen Hiragana -Zeichen als „to-u-ki- yo -u“ (とうきょう) geschrieben , wobei die übliche Sortierreihenfolge dieser Zeichen verwendet wird.

Darüber hinaus können chinesische Schriftzeichen auch nach Strichanzahl sortiert werden . In Großchina ist die Sortierung nach Nachnamenstrich in einigen offiziellen Dokumenten üblich, in denen Personennamen ohne Hierarchie aufgelistet werden.

Automatisierung

Bei der Speicherung von Informationen in digitalen Systemen kann die Sortierung automatisiert werden. Dann ist es notwendig, einen geeigneten Sortieralgorithmus zu implementieren , der die Informationen für die jeweilige Anwendung zufriedenstellend sortiert. Häufig besteht das Ziel darin, eine alphabetische oder numerische Ordnung gemäß den in den vorangegangenen Abschnitten beschriebenen Standardkriterien zu erreichen. Allerdings lassen sich nicht alle diese Kriterien leicht automatisieren. [ 3 ]

Die einfachste Form der automatischen Sortierung basiert auf den numerischen Codes der Symbole eines Zeichensatzes , wie beispielsweise der ASCII -Codierung (oder einer ihrer Erweiterungen wie Unicode ). Die Symbole werden dabei in aufsteigender Reihenfolge ihrer numerischen Codes geordnet. Diese Ordnung wird gemäß den Grundprinzipien der alphabetischen (mathematisch: lexikografischen ) Ordnung auf Zeichenketten übertragen. Ein Computerprogramm könnte die Zeichen a , b , C , d und $ also in der Reihenfolge $ , C , a , b , d behandeln (die entsprechenden ASCII-Codes sind $ = 36, a = 97, b = 98, C = 67 und d = 100). Zeichenketten, die mit C , M oder Z beginnen, würden daher vor Zeichenketten mit Kleinbuchstaben wie a , b usw. sortiert. Dies wird auch als alphabetische ASCII-Reihenfolge bezeichnet . Dies weicht von der standardmäßigen alphabetischen Reihenfolge ab, insbesondere aufgrund der Reihenfolge der Großbuchstaben vor allen Kleinbuchstaben (und möglicherweise der Behandlung von Leerzeichen und anderen Nicht-Buchstaben). Daher wird es oft mit gewissen Anpassungen angewendet, wobei die offensichtlichste die Umwandlung in Großbuchstaben (oft in Großbuchstaben, aus historischen Gründen [ Anmerkung 1 ] ) vor dem Vergleich der ASCII-Werte ist.

Viele Sortieralgorithmen vergleichen Zeichen nicht anhand ihrer numerischen Codes, sondern anhand der Sortierfolge – der Reihenfolge, in der die Zeichen für die Sortierung vorliegen – sowie weiterer, für die jeweilige Anwendung relevanter Ordnungsregeln. Dadurch können die korrekten Konventionen für die alphabetische Sortierung der betreffenden Sprache angewendet werden, wobei Groß- und Kleinschreibung, Sonderzeichen , Digraphen , Abkürzungen usw. korrekt berücksichtigt werden, wie oben unter „Alphabetische Sortierung“ und ausführlich im Artikel „Alphabetische Sortierung“ beschrieben . Solche Algorithmen können recht komplex sein und unter Umständen mehrere Durchläufe des Textes erfordern. [ 3 ]

Probleme treten dennoch häufig auf, wenn der Algorithmus mehr als eine Sprache umfassen muss. Beispielsweise steht in deutschen Wörterbüchern das Wort ökonomisch zwischen offenbar und olfaktorisch , während türkische Wörterbücher o und ö als unterschiedliche Buchstaben behandeln und oyun vor öbür einordnen .

Ein Standardalgorithmus zum Sortieren beliebiger Zeichenketten aus Unicode- Zeichen ist der Unicode-Sortieralgorithmus . Dieser kann durch Anpassung der Standard-Sortiertabelle an die jeweilige Sprache angepasst werden. Verschiedene solcher Anpassungen sind im Common Locale Data Repository ( CLDR) zu finden .

Sortierschlüssel

In manchen Anwendungen können die Zeichenketten, nach denen Elemente sortiert werden, von den angezeigten Kennungen abweichen. Beispielsweise könnte „The Shining“ als „Shining, The“ sortiert werden (siehe Alphabetische Reihenfolge oben), die Anzeige als „The Shining“ ist aber möglicherweise gewünscht . In diesem Fall können zwei Zeichenkettensätze gespeichert werden: einer für die Anzeige und einer für die Sortierung. Die so verwendeten Zeichenketten werden als Sortierschlüssel bezeichnet .

Probleme mit Zahlen

Manchmal ist es erwünscht, Text mit eingebetteten Zahlen in der korrekten numerischen Reihenfolge zu sortieren. Beispielsweise soll „Abbildung 7b“ vor „Abbildung 11a“ stehen, obwohl die '7' in Unicode nach der '1' folgt . Dies lässt sich auch auf römische Zahlen übertragen . Solange nur ganze Zahlen sortiert werden sollen, ist dieses Verhalten relativ einfach zu realisieren, allerdings kann es die Sortierung deutlich verlangsamen. Microsoft Windows verwendet dieses Verfahren beispielsweise beim Sortieren von Dateinamen . Die zugrunde liegende Sortierreihenfolge wird als natürliche Sortierreihenfolge bezeichnet .

Das korrekte Sortieren von Dezimalzahlen ist etwas schwieriger, da verschiedene Länder und Regionen unterschiedliche Symbole für den Dezimaltrennzeichen verwenden und manchmal dasselbe Zeichen, das als Dezimaltrennzeichen dient , auch als Trennzeichen verwendet wird, beispielsweise in „Abschnitt 3.2.5“. Es gibt keine allgemeingültige Lösung für das Sortieren solcher Zeichenketten; alle Regeln sind anwendungsabhängig.

Etikettierung der bestellten Artikel

In manchen Kontexten dienen Zahlen und Buchstaben weniger der Festlegung einer Reihenfolge, sondern vielmehr der Kennzeichnung bereits geordneter Elemente. So werden beispielsweise Seiten, Abschnitte, Kapitel und ähnliches sowie Listenelemente häufig auf diese Weise „nummeriert“. Als Kennzeichnungsreihen können arabische Ziffern (1, 2, 3, ...), römische Ziffern (I, II, III, ... oder i, ii, iii, ...) oder Buchstaben (A, B, C, ... oder a, b, c, ...) verwendet werden. (Alternativ lassen sich Listenelemente auch ohne Nummerierung in Stichpunkten darstellen .)

Wenn Buchstaben eines Alphabets zur Zählung verwendet werden , gelten sprachspezifische Konventionen hinsichtlich der zu verwendenden Buchstaben. Beispielsweise werden die russischen Buchstaben Ъ und Ь (die in der Schrift nur zur Modifizierung des vorhergehenden Konsonanten verwendet werden ) sowie üblicherweise auch Ы , Й und Ё weggelassen. Auch in vielen Sprachen, die eine erweiterte lateinische Schrift verwenden , werden die modifizierten Buchstaben häufig nicht zur Zählung verwendet.

Siehe auch

Anmerkungen

  1. ^ Historisch gesehen konnten Computer nur Texte in Großbuchstaben verarbeiten (dies geht auf die Konventionen der Telegrafie zurück ).

Referenzen

  1. ^ Abu-Haidar, J. A. (1983). „Rezension von A Dictionary of Modern Written Arabic (Arabic-English)“. Bulletin of the School of Oriental and African Studies, University of London . 46 (2): 351–353 . doi : 10.1017/S0041977X00079040 . ISSN  0041-977X . JSTOR  615409 .
  2. ^ „Hans Wehr Arabic-English Dictionary“ . ejtaal.net . Abgerufen am 4. Juni 2023 .
  3. ^ a b M Programmierung: Ein umfassender Leitfaden , Richard F. Walters, Digital Press, 1997