Eine Liste sortieren und entdoppeln, ohne Überraschungen

Sortieren und Entdoppeln sehen aus wie die zwei einfachsten Dinge, die du mit einer Liste tun kannst, und genau deshalb sind die Ergebnisse so oft still und leise falsch. Beides beruht auf einem Vergleich, und es gibt keine einzelne Antwort darauf, was zwei Zeilen gleich macht oder eine Zeile zuerst kommen lässt.

Lexikografische Reihenfolge ist keine numerische Reihenfolge

Der Standardvergleich für Text läuft zwei Zeichenketten Zeichen für Zeichen ab, vergleicht Codepunkte und hört beim ersten Unterschied auf. Nichts daran weiß, was eine Zahl ist.

input:   img1.png, img2.png, img10.png
sorted:  img1.png, img10.png, img2.png

img10.png landet an zweiter Stelle, weil beim vierten Zeichen 1 (U+0031) kleiner ist als 2 (U+0032) und der Vergleich dort endet. Dieselbe Regel stellt Version 1.10 vor 1.9 und listet einen Ordner voller Screenshots außerhalb der Reihenfolge auf, in der sie aufgenommen wurden.

Der numerische Vergleich behebt auch die negativen Zahlen: Lexikografisch fällt -10 zwischen -1 und -2, weil ein Minuszeichen nur ein weiteres Zeichen mit einem Codepunkt ist.

Großbuchstaben vor Kleinbuchstaben, und andere Überraschungen mit Codepunkten

In ASCII belegen Großbuchstaben 65 bis 90 und Kleinbuchstaben 97 bis 122, jeder Großbuchstabe sortiert also vor jedem Kleinbuchstaben.

Ziffern liegen unter allen Buchstaben, das Leerzeichen (32) unter jedem druckbaren Zeichen und eine leere Zeile noch darunter; eine aufsteigende Sortierung sammelt leere und mit Leerzeichen beginnende Zeilen also ganz oben und eine absteigende ganz unten.

Nachlaufender Leerraum ist die unsichtbare Fassung desselben Problems: apple und apple sortieren nebeneinander und sehen aus wie ein Duplikat, das sich partout nicht entfernen lässt. Das geschützte Leerzeichen (U+00A0) ist schlimmer, es wird identisch zu einem normalen Leerzeichen gezeichnet, sortiert aber über jedem Buchstaben, und ebenso der Wagenrücklauf, der übrig bleibt, wenn eine Windows-Datei allein an Zeilenumbrüchen aufgeteilt wird. Wenn zwei Zeilen identisch aussehen und trotzdem nicht zusammenfallen, prüfe auf versteckte Zeichen.

Dieselbe Liste sortiert sich in zwei Ländern verschieden

Die Reihenfolge nach Codepunkt stellt außerdem jedes akzentuierte Zeichen hinter jedes nicht akzentuierte. Zürich sortiert hinter Zzz und Ärger hinter zebra. Keine Sprache ordnet ihr eigenes Alphabet so. Eine locale-bewusste Kollation vergleicht stattdessen nach Sprachregeln, und diese Regeln widersprechen einander.

In JavaScript steckt das in Intl.Collator:

const words = ["Zebra", "Ärger", "Apfel"];

words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra

words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger

Dasselbe Objekt deckt die früheren Probleme mit ab. { numeric: true } vergleicht Ziffernfolgen als Zahlen, das ist die natürliche Reihenfolge, und sensitivity legt fest, was als Unterschied zählt: "base" ignoriert Schreibweise und Akzente, "accent" ignoriert nur die Schreibweise, "case" ignoriert nur die Akzente. Die Locale wegzulassen nimmt das, worauf die Maschine eingestellt ist, und so liefert derselbe Code auf zwei Laptops zwei verschiedene Reihenfolgen. Benenne die Locale, wenn die Ausgabe überall übereinstimmen muss.

Welche Duplikate als Duplikate zählen

Das Entdoppeln ist nur so genau definiert wie der Gleichheitstest dahinter. Nimm fünf Zeilen, die sich alle als das Wort cafe mit einem Akut darstellen:

Vier vernünftige Regeln geben vier verschiedene Antworten:

Keine davon ist falsch; sie beantworten verschiedene Fragen. Die Normalisierung zählt mehr, als es aussieht, denn Text aus macOS-Dateinamen kommt meist zerlegt (NFD) an und Text aus Windows und Webformularen zusammengesetzt (NFC), eine aus zwei Quellen eingefügte Liste sammelt also unsichtbare Zwillinge ein. NFKC geht weiter und faltet Kompatibilitätszeichen wie die Ligatur fi in ihre schlichten Entsprechungen.

Konventionell gewinnt das erste Vorkommen; wenn also die unsaubere Kopie zuerst eingefügt wurde, überlebt sie. Und Duplikate zu entfernen ist eine andere Anforderung, als eindeutige Einträge zu finden: Remove Duplicate Lines lässt von jedem einen übrig, während die eindeutige Menge in List Frequency die kleinere Gruppe der Einträge ist, die genau einmal vorkommen.

Stabilität, und nach zwei Schlüsseln sortieren

Eine stabile Sortierung garantiert, dass Einträge, die der Vergleicher als gleich einstuft, die Reihenfolge behalten, die sie in der Eingabe hatten. Genau das lässt das Sortieren nach mehreren Schlüsseln in wiederholten Durchgängen funktionieren: Sortiere zuerst nach dem unwichtigsten Schlüssel, dann nach dem wichtigsten. Nach Name und danach nach Abteilung zu sortieren ergibt geordnete Abteilungen mit geordneten Namen innerhalb jeder einzelnen. Eine instabile Sortierung macht den ersten Durchgang zunichte, während sie den zweiten ausführt, und das Ergebnis sieht fast richtig aus, was schlimmer ist, als falsch auszusehen.

Das Umkehren trägt denselben Haken, denn eine sortierte Liste umzudrehen dreht auch jede Gruppe gleichrangiger Einträge um. Nimm Reverse List, wenn du die gesamte Reihenfolge umdrehen willst, nicht als Abkürzung zu einer absteigenden Sortierung.

Die Implementierungen unterscheiden sich. Für Array.prototype.sort in JavaScript ist Stabilität erst seit ES2019 vorgeschrieben; davor benutzte V8 oberhalb einer kleinen Arraygröße einen instabilen Quicksort, derselbe Code verhielt sich also bei zehn Einträgen anders als bei zehntausend. Das sorted von Python ist stabil, und GNU sort ist es nicht, sofern es nicht -s bekommt.

Mischen ist keine Art des Sortierens

Das Einzeiler-Mischen, list.sort(() => Math.random() - 0.5), ist verzerrt. Eine Sortierung geht davon aus, dass ihr Vergleicher eine widerspruchsfreie Ordnung beschreibt, und fragt nur nach der Teilmenge der Paare, die ihr Algorithmus braucht. Ein Vergleicher, der bei jedem Aufruf eine frische Zahl würfelt, bricht diese Annahme, das Ergebnis hängt also vom Algorithmus und von der Arraylänge ab: Einträge bleiben eher in der Nähe ihres Ausgangsplatzes, und manche Permutationen tauchen weit häufiger auf als andere.

Ein korrektes Mischen nutzt Fisher-Yates: vom Ende her durchlaufen und jeden Eintrag mit einem gleichverteilt gewählten Eintrag an oder vor seiner Position tauschen:

for (let i = list.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [list[i], list[j]] = [list[j], list[i]];
}

Die verbreitete kaputte Variante nutzt Math.random() * list.length innerhalb der Schleife und zieht damit jedes Mal aus dem gesamten Array. Das ergibt n hoch n gleich wahrscheinliche Zugfolgen, was sich nicht gleichmäßig durch die n-Fakultät Anordnungen teilen lässt, manche Anordnungen kommen also häufiger vor.

Zufall und Sortieren lassen sich korrekt verbinden, indem du jedem Eintrag vorab einen Zufallsschlüssel gibst und nach diesem Schlüssel sortierst, denn dann bleibt der Vergleicher widerspruchsfrei. Der Fehler liegt darin, im Vergleich selbst zu würfeln.

Die Reihenfolge der Schritte

Die meisten Listenprobleme kommen daher, dass die richtigen Operationen in der falschen Reihenfolge ausgeführt werden.

1. Zuerst auspacken. Eine aus Code kopierte Liste kommt als "apple", an; die Anführungszeichen und das Komma gehören zur Zeichenkette, sie passt also nie auf apple. Unwrap List Items entfernt sie.
2. Trimmen und normalisieren, damit Gleichheit das bedeutet, was du darunter verstehst.
3. Entdoppeln, mit einer bewusst gewählten Übereinstimmungsregel statt einer übernommenen Voreinstellung.
4. Sortieren. Sort Lines deckt Text, Zahlen, Länge und Zufallsreihenfolge ab; ergänze eine Locale für Daten mit Akzenten.
5. Zuletzt umformen. Group List Items schneidet das Ergebnis in Blöcke fester Größe für ein Limit pro Anfrage, und Rotate List verschiebt alles weiter, ohne die innere Reihenfolge zu ändern.

Vor dem Trimmen zu entdoppeln lässt Beinahe-Duplikate zurück, und vor dem Entdoppeln zu sortieren sortiert nur Zeilen, die gleich weggeworfen werden.