Een lijst sorteren en ontdubbelen zonder verrassingen

Sorteren en ontdubbelen lijken de twee eenvoudigste dingen die je met een lijst kunt doen, en juist daarom zijn de resultaten zo vaak stilletjes verkeerd. Beide steunen op een vergelijking, en er is geen enkel antwoord op de vraag wat twee regels gelijk maakt of welke regel voorop komt.

Lexicografische volgorde is geen numerieke volgorde

De standaardvergelijking voor tekst loopt twee strings teken voor teken af, vergelijkt code points, en stopt bij het eerste verschil. Niets daarin weet wat een getal is.

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

img10.png belandt op de tweede plek omdat bij het vierde teken 1 (U+0031) lager is dan 2 (U+0032), en de vergelijking daar eindigt. Dezelfde regel zet versie 1.10 vóór 1.9, en toont een map met schermafbeeldingen niet in de volgorde waarin ze gemaakt zijn.

Numeriek vergelijken lost ook negatieve getallen op: lexicografisch valt -10 tussen -1 en -2, want een minteken is gewoon nog een teken met een code point.

Hoofdletters vóór kleine letters, en andere verrassingen met code points

In ASCII bezetten hoofdletters 65 tot 90 en kleine letters 97 tot 122, dus elke hoofdletter komt vóór elke kleine letter.

Cijfers staan onder alle letters, de spatie (32) onder elk afdrukbaar teken, en een lege regel daaronder, dus een oplopende sortering verzamelt lege regels en regels die met een spatie beginnen helemaal bovenaan, en een aflopende sortering verzamelt ze onderaan.

Witruimte aan het eind is de onzichtbare versie van hetzelfde probleem: apple en apple sorteren naast elkaar en zien eruit als een duplicaat dat weigert verwijderd te worden. De non-breaking space (U+00A0) is erger, want die wordt identiek getekend aan een normale spatie maar sorteert boven elke letter, net als de carriage return die achterblijft wanneer een Windows-bestand alleen op newlines gesplitst wordt. Als twee regels identiek ogen en toch niet samenvallen, zoek dan naar verborgen tekens.

Dezelfde lijst sorteert in twee landen verschillend

De volgorde op code point zet ook elk teken met accent na elk teken zonder. Zürich komt na Zzz, en Ärger na zebra. Geen enkele taal ordent zijn eigen alfabet zo. Collatie die rekening houdt met de landinstelling vergelijkt volgens taalregels, en die regels spreken elkaar tegen.

In JavaScript zit dit 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

Hetzelfde object dekt de eerdere problemen af. { numeric: true } vergelijkt reeksen cijfers als getallen, wat natuurlijke volgorde is, en sensitivity bepaalt wat als verschil telt: "base" negeert hoofdletters en accenten, "accent" negeert alleen hoofdletters, "case" negeert alleen accenten. De landinstelling weglaten gebruikt wat de machine ingesteld heeft, en zo levert dezelfde code op twee laptops twee verschillende volgordes op. Noem de landinstelling wanneer de uitvoer overal hetzelfde moet zijn.

Welke duplicaten als duplicaat tellen

Ontdubbelen is precies zo goed gedefinieerd als de gelijkheidstest erachter. Neem vijf regels die allemaal als het woord cafe met een accent aigu weergegeven worden:

Vier redelijke regels geven vier verschillende antwoorden:

Geen ervan is fout; ze beantwoorden verschillende vragen. Normalisatie telt zwaarder dan het lijkt, want tekst uit macOS-bestandsnamen komt vaak ontleed binnen (NFD) en tekst uit Windows en webformulieren samengesteld (NFC), dus een lijst die uit twee bronnen geplakt is, krijgt onzichtbare tweelingen. NFKC gaat verder en vouwt compatibiliteitstekens zoals de ligatuur fi samen tot hun gewone equivalent.

Per conventie wint het eerste voorkomen, dus als de slordige kopie eerst geplakt is, overleeft die. En duplicaten verwijderen is een ander verzoek dan unieke items vinden: Remove Duplicate Lines laat er van elk één staan, terwijl de unieke verzameling in List Frequency de kleinere groep is van items die precies één keer voorkomen.

Stabiliteit, en sorteren op twee sleutels

Een stabiele sortering garandeert dat items die de comparator gelijk noemt de volgorde behouden die ze in de invoer hadden. Dat is wat sorteren op meerdere sleutels via herhaalde doorgangen mogelijk maakt: sorteer eerst op de minst belangrijke sleutel, daarna op de belangrijkste. Sorteren op naam en vervolgens op afdeling geeft afdelingen op volgorde, met namen op volgorde binnen elke afdeling. Een instabiele sortering maakt de eerste doorgang ongedaan tijdens de tweede, en het resultaat ziet er bijna goed uit, wat erger is dan er verkeerd uitzien.

Omkeren heeft dezelfde valstrik, want een gesorteerde lijst omdraaien keert ook elke groep gelijke items om. Gebruik Reverse List wanneer je de hele volgorde wilt omdraaien, niet als kortere weg naar een aflopende sortering.

Implementaties verschillen. Array.prototype.sort in JavaScript hoeft pas sinds ES2019 stabiel te zijn; daarvoor gebruikte V8 boven een kleine arraygrootte een instabiele quicksort, dus dezelfde code gedroeg zich anders bij tien items dan bij tienduizend. De sorted van Python is stabiel, en GNU sort is dat niet, tenzij je -s meegeeft.

Shuffelen is geen vorm van sorteren

De shuffle van één regel, list.sort(() => Math.random() - 0.5), is vertekend. Een sortering gaat ervan uit dat haar comparator een consistente volgorde beschrijft, en vraagt alleen naar de deelverzameling van paren die het algoritme nodig heeft. Een comparator die bij elke aanroep een vers getal trekt breekt die aanname, dus het resultaat hangt af van het algoritme en de arraylengte: items blijven doorgaans in de buurt van waar ze begonnen, en sommige permutaties komen veel vaker voor dan andere.

Een correcte shuffle gebruikt Fisher-Yates, waarbij je vanaf het einde loopt en elk item verwisselt met een uniform gekozen item op of vóór die positie:

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]];
}

De veelgemaakte kapotte variant gebruikt Math.random() * list.length binnen de lus en trekt dus elke keer uit de hele array. Dat geeft n tot de macht n even waarschijnlijke reeksen trekkingen, en dat is niet gelijkmatig deelbaar door de n faculteit mogelijke volgordes, dus sommige volgordes komen vaker voor.

Willekeur en sorteren zijn wel correct te combineren door elk item vooraf één willekeurige sleutel te geven en daarop te sorteren, want dan blijft de comparator consistent. De fout zit in het gooien van de dobbelsteen binnen de vergelijking.

De volgorde waarin de stappen gaan

De meeste problemen met lijsten komen doordat de juiste bewerkingen in de verkeerde volgorde worden uitgevoerd.

1. Pel eerst uit. Een lijst die uit code gekopieerd is, komt binnen als "apple",; de aanhalingstekens en de komma horen bij de string, dus hij komt nooit overeen met apple. Unwrap List Items haalt ze weg.
2. Trim en normaliseer, zodat gelijkheid betekent wat jij denkt dat het betekent.
3. Ontdubbel, met de vergelijkingsregel bewust gekozen in plaats van als standaard overgenomen.
4. Sorteer. Sort Lines dekt tekst, numeriek, lengte en willekeurige volgorde; voeg een landinstelling toe voor data met accenten.
5. Hervorm als laatste. Group List Items knipt het resultaat in batches van vaste grootte voor een limiet per verzoek, en Rotate List schuift alles op zonder de onderlinge volgorde te veranderen.

Ontdubbelen vóór het trimmen laat bijna-duplicaten staan, en sorteren vóór het ontdubbelen sorteert alleen maar rijen die zo meteen weggegooid worden.