Die lexikographische Ordnung ist in der Informatik und Mathematik eine Methode, um aus Ordnungen für einfache Objekte (beispielsweise Buchstaben) eine Ordnung für zusammengesetzte Objekte (beispielsweise Wörter) zu erhalten. Das namengebende Beispiel ist die Anordnung der Wörter in einem Lexikon: Sie werden zunächst nach ihren Anfangsbuchstaben sortiert, dann die Wörter mit gleichen Anfangsbuchstaben nach dem jeweils zweiten Buchstaben usw. Ist ein Wort ganz in einem anderen als Anfangsteil enthalten (wie beispielsweise „Tal“ in „Talent“), so wird das kürzere Wort zuerst aufgeführt.

Formal kann diese Ordnung wie folgt beschrieben werden: Eine Zeichenkette $a$ ist kleiner als eine Zeichenkette $b$ (d. h. $a$ liegt in der Sortierung vor $b$), wenn

• entweder das erste Zeichen von $a$, in dem sich beide Zeichenketten unterscheiden, kleiner ist als das entsprechende Zeichen von $b$,
• oder wenn $a$ den Anfang von $b$ bildet, aber kürzer ist.

Häufig wird diese Ordnung auch bei endlichen Folgen einer festen Länge verwendet, beispielsweise bei Paaren: Ein Paar $(a\_1,a\_2)$ ist dann kleiner als ein Paar $(b\_1,b\_2)$, wenn

• entweder
• oder $a\_1=b\_1$ und

Ein Beispiel für eine derartige Ordnung ist die zeitliche Reihenfolge für Zahlentripel (Jahr, Monat, Tag): Ein Datum X ist früher als ein anderes Datum Y, wenn

• entweder die Jahreszahl von X kleiner ist als die Jahreszahl von Y
• oder die Jahreszahlen gleich sind, aber X in einem im Jahresverlauf früheren Monat liegt
• oder die Jahreszahlen und Monate gleich sind, aber der Tag von X kleiner als der Tag von Y ist.

Ordnungstheorie | Theoretische Informatik

Lexicographical order | Orden lexicográfico | Ordine lessicografico | Porządek leksykograficzny | Lexikografisk ordning