Text sortieren ist nicht eine Operation: vier Reihenfolgen, die sich alle alphabetisch nennen

Vier Dinge, die alphabetisch heißen

Eine Sortier-Schaltfläche bietet eine Option an und legt nahe, es gebe eine Antwort. Es gibt mindestens vier, und sie sind keine Verfeinerungen voneinander: Es sind verschiedene Reihenfolgen, die aus derselben Eingabe verschiedene Listen zurückgeben. Die Codeeinheiten-Ordnung vergleicht die Zahlenwerte der UTF-16-Einheiten, aus denen eine Zeichenkette besteht. Die natürliche Ordnung liest Ziffernfolgen als Zahlen. Die Locale-Kollation wendet die Regeln einer Sprache darauf an, welche Buchstaben als derselbe Buchstabe zählen. Kollationsvarianten spalten eine einzelne Sprache dann noch in mehrere vertretbare Ordnungen, denn deutsche Wörterbücher und deutsche Telefonbücher waren sich nie einig.

Alles Folgende wurde ausgeführt, nicht erinnert. Jede Liste ist genau so abgedruckt, wie Node 26.3 sie zurückgegeben hat, und die Skripte sind kurz genug zum Abtippen: ein Array, ein sort, ein console.log.

Codeeinheiten-Ordnung: was .sort() tatsächlich tut

Ohne Vergleichsfunktion aufgerufen, wandelt Array.prototype.sort jedes Element in eine Zeichenkette um und vergleicht diese nach UTF-16-Codeeinheiten. Das ist eine dokumentierte Regel, kein Zufall, und sie erzeugt zwei sichtbare Symptome. Großbuchstaben liegen im Bereich 0x41–0x5A, Kleinbuchstaben in 0x61–0x7A, also steht jeder Großbuchstabe vor jedem Kleinbuchstaben. Und Ziffern werden als Zeichen verglichen: ['Kapitel10','Kapitel9','Kapitel2'] liefert Kapitel10, Kapitel2, Kapitel9, denn „1“ ist 0x31 und „9“ ist 0x39, und der Vergleich endet bei der ersten Abweichung.

Das dritte Symptom ist jenes, das bei Leserinnen und Lesern ankommt. Jeder Buchstabe mit diakritischem Zeichen liegt oberhalb von 0x7A, also schiebt die Codeeinheiten-Ordnung das gesamte akzentuierte Alphabet hinter das z. ["Öl","Ohr","Zebra","Ähre"] liefert Ohr, Zebra, Ähre, Öl. ["ñu","nube","niño","zorro"] liefert niño, nube, zorro, ñu. ["ação","acordo","água","avô"] liefert acordo, avô, ação, água. ["étage","effet","zèbre","Île"] liefert effet, zèbre, Île, étage. Vier Sprachen, vier falsche Antworten, eine Zeile Code.

Die Codeeinheiten-Ordnung ist nicht nutzlos. Sie ist total, transparent, schnell - 20 000 Wörter in 6 ms im Benchmark weiter unten - und in jeder Laufzeitumgebung und jeder Locale identisch, was sie zur richtigen Wahl für alles macht, was eine Maschine liest: Indexschlüssel, Deduplizierungs-Buckets, Cache-Kennungen, kanonische Serialisierungen. Falsch ist sie nur, wenn die Ausgabe für einen Menschen bestimmt ist.

Natürliche Ordnung: Ziffern als Zahlen lesen

Die natürliche Ordnung - jene, die ein Dateimanager verwendet - behandelt eine Ziffernfolge innerhalb einer Zeichenkette als eine einzige Zahl statt als Zeichenfolge. In JavaScript ist sie eine Option: new Intl.Collator("de", { numeric: true }). Auf ["Kapitel10","Kapitel9","Kapitel2"] liefert sie Kapitel2, Kapitel9, Kapitel10, und auf der längeren Liste ["item2","item9","item10","item100","item20"] liefert sie item2, item9, item10, item20, item100, während das voreingestellte .sort() item10, item100, item2, item20, item9 liefert.

Zwei Grenzen sollte man kennen, bevor man sie überall einschaltet. Numerische Kollation ist eine Darstellungsbequemlichkeit, keine Arithmetik: Sie vergleicht Ziffernfolgen, hat also über „v1.10“ gegen „v1.9“ eine Meinung, die ein Parser für semantische Versionen nicht teilen würde, und sie sagt nichts Brauchbares über Vorzeichen, Dezimal- oder Tausendertrennzeichen. Und sie ändert die Antwort für Schlüssel, die bloß zufällig Ziffern enthalten, etwa Produktcodes, bei denen 0090 und 90 verschiedene Artikel sind. Schalte sie für Listen ein, die ein Mensch überfliegt, und für Kennungen aus.

Locale-Kollation: Deutsch gegen Schwedisch

Die Locale-Kollation ist der klassische Fall, und Deutsch gegen Schwedisch ist das klassische Paar. Nimm ["Öl","Ohr","Zebra","Ähre"]. Unter new Intl.Collator("de") sortiert die Liste als Ähre, Ohr, Öl, Zebra: ä ist eine Variante von a, ö eine Variante von o, und das diakritische Zeichen entscheidet nur Gleichstände. Unter new Intl.Collator("sv") ergeben dieselben vier Zeichenketten Ohr, Zebra, Ähre, Öl: Im Schwedischen sind å, ä und ö die letzten drei Buchstaben des Alphabets, hinter dem z. Keines von beiden ist ein Fehler. Es sind zwei Sprachen mit zwei Alphabeten, und die Liste muss sich für eines entscheiden.

Jetzt der unangenehme Teil: Für diese Liste liefert das voreingestellte .sort() Ohr, Zebra, Ähre, Öl - Zeichen für Zeichen die schwedische Antwort. Ein Programm, das die Locale ausgelassen hat, hat nicht „keine bestimmte Reihenfolge“ erzeugt. Es hat stillschweigend eine bestimmte fremde Reihenfolge erzeugt, und es wird das für jede deutsche, spanische, portugiesische und französische Liste weiter tun, die es anfasst.

Die übrigen Locales dieses Artikels verhalten sich genauso. Spanisch macht ñ zu einem eigenen Buchstaben nach n: ["ñu","nube","niño","zorro"] ergibt unter es niño, nube, ñu, zorro, während die Codeeinheiten-Ordnung ñu hinter zorro verbannt. Portugiesisch behandelt Akzente als Gleichstandsbrecher: ["ação","acordo","água","avô"] kommt unter pt in Wörterbuchreihenfolge heraus und unter .sort() durcheinander. Italienisch ergibt unter it ancora, Àncora, elite, zucchero, wobei der Akzent eine sekundäre und die Großschreibung eine tertiäre Differenz ist. Und Französisch hat eine wirklich regionale Ordnung: Auf ["cote","coté","côte","côté"] liefert fr cote, coté, côte, côté, fr-CA dagegen cote, côte, coté, côté, weil das kanadische Französisch Akzente vom Wortende her vergleicht.

Eine Sprache, mehrere Ordnungen: Kollationsvarianten

Selbst innerhalb einer Sprache gibt es mehr als eine richtige Antwort, und das CLDR von Unicode liefert sie als benannte Varianten, die über die Locale-Zeichenkette gewählt werden. Deutsch hat zwei im täglichen Gebrauch. Die Wörterbuch-Kollation de sortiert ['Göbel','Goethe','Godel','Gözde','Gott'] als Göbel, Godel, Goethe, Gott, Gözde: ö ist eine Variante von o. Die Telefonbuch-Kollation de-u-co-phonebk sortiert dieselben fünf als Godel, Göbel, Goethe, Gözde, Gott, weil ö zu oe expandiert wird - womit Göbel zwischen Godel und Goethe steht, genau dort, wo jemand nachschlägt, der „Goebel“ sucht.

Neben der Variante stehen zwei Regler, die die Antwort ebenso stark verändern. sensitivity entscheidet, welche Unterschiede überhaupt zählen: Bei „cote“ gegen „côte“ und „cote“ gegen „Cote“ meldet die Sensitivität „base“ beide Paare als gleich, „accent“ trennt den Akzent, aber nicht die Groß- und Kleinschreibung, „case“ trennt die Schreibung, aber nicht den Akzent, und „variant“ - die Voreinstellung - trennt beides. caseFirst entscheidet, wer einen Gleichstand gewinnt: Bei ['apple','Apple','APPLE'] liefert die Voreinstellung apple, Apple, APPLE, und caseFirst: 'upper' liefert APPLE, Apple, apple. Keiner der Regler ist Kosmetik. sensitivity macht einen Kollator außerdem zum Suchwerkzeug: Mit „base“ gibt compare 0 für Zeichenketten zurück, die eine Leserin dasselbe Wort nennen würde.

Stabilität: was mit Gleichständen geschieht

Eine Sortierung ist stabil, wenn Elemente, die als gleich verglichen werden, ihre relative Reihenfolge aus der Eingabe behalten. Das zählt in dem Moment, in dem man nach einem Teilschlüssel sortiert - einem Anfangsbuchstaben, einer Kategorie, einem Datum ohne Uhrzeit -, denn Gleichstände sind keine seltenen Randfälle, sie sind der größte Teil der Liste. Beim Sortieren von zehn Vornamen allein nach ihrem Anfangsbuchstaben kamen die Elemente mit a in den Eingabepositionen 1, 2, 4, 6, 8 heraus und die mit b in den Positionen 0, 3, 5, 7, 9: jede Gruppe erhalten, in Reihenfolge.

Array.prototype.sort muss laut Spezifikation seit ES2019 stabil sein. Davor durften Engines oberhalb einer bestimmten Arraylänge einen instabilen Algorithmus verwenden, und mehrere taten das - deshalb raten ältere Texte zu einem zusammengesetzten Vergleicher oder dazu, den Index mitzuführen. Die Anforderung gilt unabhängig von der Größe: Ein Array mit tausend Elementen, sortiert nach einem Schlüssel mit nur drei verschiedenen Werten, kam mit jeder Gruppe in Eingabereihenfolge zurück. Du kannst deshalb eine Mehrschlüssel-Sortierung bauen, indem du mehrfach sortierst, vom unwichtigsten Schlüssel zum wichtigsten - erst Vorname, dann Nachname - und sich darauf verlassen, dass die früheren Durchgänge überleben.

Was es kostet, und die Regel, die folgt

Locale-bewusstes Sortieren kostet mehr als Codeeinheiten-Sortieren, aber nicht so viel, wie befürchtet wird, und der teure Fehler ist ein anderer. 20 000 Wörter in Node 26.3 sortiert: Das voreingestellte .sort() brauchte 6 ms, a.localeCompare(b, "de") 12 ms, ein einmal gebauter und wiederverwendeter Kollator 28 ms - und ein new Intl.Collator, im Vergleicher selbst konstruiert, brauchte 1 771 ms, sechzigmal langsamer als die Wiederverwendung. Der Kostenpunkt ist nicht die Kollation. Der Kostenpunkt ist, den Kollator hunderttausendfach zu bauen.

Bleibt eine Regel, kurz genug, um sie anzuwenden. Liest eine Maschine die Ausgabe, sortierst du nach Codeeinheiten und schreibst es auf. Liest ein Mensch sie, nennst du eine Locale - die Sprache, in der das Dokument geschrieben ist, nicht die des Browsers, der es zufällig darstellt -, bau einen Intl.Collator, entscheide numeric und sensitivity bewusst und verwende ihn wieder. Nie vertretbar ist nur das eine: .sort() auf sichtbaren Text anzuwenden und das Ergebnis alphabetisch zu nennen.

Häufige Fragen

Warum wird „Zebra“ vor „apple“ einsortiert?

Weil .sort() ohne Vergleichsfunktion UTF-16-Codeeinheiten vergleicht und jeder ASCII-Großbuchstabe (0x41–0x5A) einen kleineren Wert hat als jeder ASCII-Kleinbuchstabe (0x61–0x7A). Es sortiert keine Buchstaben, es sortiert Zahlen, die zufällig Buchstaben darstellen. Jeder Locale-Kollator behebt das: new Intl.Collator("en").compare liefert apple, Banana, zebra, Zebra in dieser Reihenfolge und behandelt die Groß- und Kleinschreibung als letzten Gleichstandsbrecher statt als erstes Kriterium.

Ist die Sortierung von JavaScript stabil?

Ja, und sie muss es sein. ES2019 hat Stabilität für Array.prototype.sort zur Spezifikationsanforderung gemacht, und Array.prototype.toSorted folgt derselben Regel. Hier an einem Array mit tausend Elementen überprüft, sortiert nach einem Schlüssel mit drei verschiedenen Werten: Jede Gruppe kam in Eingabereihenfolge zurück. Diese Garantie erlaubt es, eine mehrspaltige Sortierung als Folge einspaltiger Sortierungen umzusetzen, beginnend mit der unwichtigsten Spalte.

Welche Locale nehme ich, wenn ich die des Lesers nicht kenne?

Nimm die Sprache des Inhalts, nicht die des Lesegeräts. Eine Liste deutscher Produktnamen gehört in deutsche Kollation, egal wer sie ansieht - genau wie ein gedruckter deutscher Katalog. Auf die Voreinstellung der Laufzeitumgebung zurückzufallen ist die schlechteste Option, weil sie unsichtbar ist: new Intl.Collator() ohne Argument löste sich auf der Maschine, auf der dieser Artikel entstand, zu en-US auf und würde sich auf der nächsten anders auflösen - dieselbe Liste ordnete sich also auf zwei Servern verschieden, ohne dass eine Zeile Code sich ändert.

Warum ordnet mein Dateimanager item2 vor item10, mein Code aber nicht?

Der Dateimanager verwendet die natürliche Ordnung: Er erkennt die Ziffernfolge als Zahl. Dein Code vergleicht Zeichen, hält also bei „1“ gegen „9“ an und liest den Rest nie. Füge einem Intl.Collator { numeric: true } hinzu oder übergib dieselbe Option an localeCompare, dann stimmen beide überein. Versuch nicht, es durch Auffüllen der angezeigten Zeichenketten mit Nullen nachzubilden - das repariert die Sortierung und zerstört die Beschriftungen.

Ist localeCompare für eine lange Liste zu langsam?

Für sich genommen nicht. Bei 20 000 Wörtern in Node 26.3 brauchte a.localeCompare(b, "de") 12 ms und ein wiederverwendeter Intl.Collator 28 ms gegenüber 6 ms für das voreingestellte .sort() - ein Unterschied, den niemand bemerkt. Wirklich langsam ist es, einen Kollator im Vergleicher zu konstruieren: So brauchte dieselbe Sortierung 1 771 ms, weil für jede der Hunderttausenden Vergleiche ein neuer Kollator gebaut wird. Bau ihn einmal außerhalb der Sortierung und übergib sein .compare.

Wie sortiere ich deutsche Namen wie ein Telefonbuch?

Fordere die Kollationsvariante namentlich an: new Intl.Collator("de-u-co-phonebk"). Der Teil -u-co- einer Locale-Kennung wählt eine Kollation aus, und phonebk ist die deutsche Telefonbuch-Anpassung, in der sich ö wie oe, ä wie ae und ü wie ue verhält. Auf ["Göbel","Goethe","Godel","Gözde","Gott"] liefert einfaches de Göbel, Godel, Goethe, Gott, Gözde und de-u-co-phonebk liefert Godel, Göbel, Goethe, Gözde, Gott. Andere Sprachen haben eigene Varianten - eine chinesische Liste lässt sich genauso nach Pinyin oder nach Strichzahl ordnen.