Att sortera och avdubblera en lista utan överraskningar

Att sortera och avdubblera ser ut som de två enklaste saker du kan göra med en lista, vilket är varför resultaten så ofta är tyst felaktiga. Båda vilar på en jämförelse, och det finns inget enda svar på vad som gör två rader lika eller vilken rad som kommer först.

Lexikografisk ordning är inte numerisk ordning

Standardjämförelsen för text vandrar genom två strängar ett tecken i taget, jämför kodpunkter och stannar vid den första skillnaden. Ingenting i den vet vad ett tal är.

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

img10.png hamnar tvåa eftersom 1 (U+0031) vid det fjärde tecknet är lägre än 2 (U+0032), och jämförelsen slutar där. Samma regel sätter version 1.10 före 1.9 och listar en mapp med skärmbilder i en annan ordning än de togs.

Numerisk jämförelse rättar också till negativa tal: lexikografiskt hamnar -10 mellan -1 och -2, eftersom ett minustecken bara är ännu ett tecken med en kodpunkt.

Versaler före gemener, och andra kodpunktsöverraskningar

I ASCII upptar versalerna 65 till 90 och gemenerna 97 till 122, så varje versal sorteras före varje gemen.

Siffror ligger under alla bokstäver, mellanslaget (32) under varje skrivbart tecken, och en tom rad under det, så en stigande sortering samlar tomma rader och rader som börjar med mellanslag allra överst, medan en fallande sortering samlar dem längst ner.

Avslutande blanktecken är den osynliga versionen av samma problem: apple och apple sorteras bredvid varandra och ser ut som en dubblett som vägrar bli borttagen. Det hårda mellanslaget (U+00A0) är värre, ritat identiskt med ett vanligt mellanslag men sorterat ovanför varje bokstav, liksom den vagnretur som blir kvar när en Windows-fil delas enbart på radmatningar. Om två rader ser identiska ut och ändå inte faller ihop, leta efter dolda tecken.

Samma lista sorteras olika i två länder

Kodpunktsordning sätter också varje accenttecken efter varje tecken utan accent. Zürich sorteras efter Zzz, och Ärger efter zebra. Inget språk ordnar sitt eget alfabet på det sättet. Språkanpassad kollationering jämför i stället efter språkets regler, och de reglerna är oense med varandra.

I JavaScript bor detta i 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

Samma objekt täcker de tidigare problemen. { numeric: true } jämför sifferföljder som tal, vilket är naturlig ordning, och sensitivity bestämmer vad som räknas som en skillnad: "base" bortser från skiftläge och accenter, "accent" bortser bara från skiftläge, "case" bortser bara från accenter. Att utelämna språkinställningen använder vad maskinen nu är inställd på, vilket är hur samma kod ger två olika ordningar på två bärbara datorer. Ange språkinställningen när utdata måste stämma överallt.

Vilka dubbletter som räknas som dubbletter

Avdubblering är bara så väldefinierad som likhetstestet bakom den. Ta fem rader som alla renderas som ordet cafe med akut accent:

Fyra rimliga regler ger fyra olika svar:

Ingen av dem är fel; de svarar på olika frågor. Normalisering spelar större roll än det ser ut, eftersom text från filnamn på macOS tenderar att anlända uppdelad (NFD) och text från Windows och webbformulär sammansatt (NFC), så en lista som klistrats in från två källor drar på sig osynliga tvillingar. NFKC går längre och slår ihop kompatibilitetstecken som ligaturen fi med sina enkla motsvarigheter.

Den första förekomsten vinner enligt konvention, så om den ostädade kopian klistrades in först är det den som överlever. Och att ta bort dubbletter är en annan begäran än att hitta unika poster: Remove Duplicate Lines lämnar kvar en av varje, medan den unika mängden i List Frequency är den mindre gruppen av poster som förekommer exakt en gång.

Stabilitet, och sortering på två nycklar

En stabil sortering garanterar att poster som komparatorn kallar lika behåller den ordning de hade i indata. Det är vad som får sortering på flera nycklar genom upprepade pass att fungera: sortera på den minst viktiga nyckeln först, sedan på den viktigaste. Att sortera på namn och sedan på avdelning ger avdelningarna i ordning, med namnen ordnade inom var och en. En instabil sortering river upp det första passet medan den gör det andra, och resultatet ser nästan rätt ut, vilket är värre än att se fel ut.

Att vända på listan bär samma hake, eftersom en vändning av en sorterad lista också vänder varje grupp av lika poster. Använd Reverse List när det du vill är att vända hela ordningen, inte som en genväg till en fallande sortering.

Implementationerna skiljer sig åt. JavaScripts Array.prototype.sort har bara varit tvungen att vara stabil sedan ES2019; dessförinnan använde V8 en instabil quicksort ovanför en viss arraystorlek, så samma kod betedde sig olika på tio poster och på tiotusen. Pythons sorted är stabil, och GNU sort är det inte om den inte får -s.

Blandning är inte en sorts sortering

Enradsblandningen list.sort(() => Math.random() - 0.5) är skev. En sortering utgår från att dess komparator beskriver en konsekvent ordning, och frågar bara om den delmängd av par som algoritmen behöver. En komparator som slår ett nytt tal vid varje anrop bryter det antagandet, så resultatet beror på algoritmen och arrayens längd: poster tenderar att stanna nära där de började, och vissa permutationer dyker upp långt oftare än andra.

En korrekt blandning använder Fisher-Yates, som vandrar från slutet och byter varje post med en likformigt vald post på eller före dess plats:

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

Den vanliga trasiga varianten använder Math.random() * list.length inuti slingan och drar ur hela arrayen varje gång. Det ger n upphöjt till n lika sannolika dragningsföljder, vilket inte går jämnt upp mot de n fakultet ordningarna, så vissa ordningar dyker upp oftare.

Slump och sortering kan kombineras korrekt genom att varje post får en slumpnyckel i förväg och sorteras på den nyckeln, eftersom komparatorn då förblir konsekvent. Felet är att slå tärningen inuti jämförelsen.

Ordningen stegen ska gå i

De flesta listproblem kommer av att rätt operationer görs i fel ordning.

1. Packa upp först. En lista som kopierats ur kod anländer som "apple",; citattecknen och kommat är en del av strängen, så den matchar aldrig apple. Unwrap List Items tar bort dem.
2. Trimma och normalisera, så att likhet betyder det du tror att den betyder.
3. Avdubblera, med matchningsregeln medvetet vald snarare än övertagen som standard.
4. Sortera. Sort Lines täcker text, numerisk ordning, längd och slumpordning; lägg till en språkinställning för accentbärande data.
5. Forma om sist. Group List Items delar resultatet i lika stora satser för en gräns per begäran, och Rotate List förskjuter allt utan att ändra den inbördes ordningen.

Att avdubblera före trimning lämnar kvar nästan-dubbletter, och att sortera före avdubblering sorterar bara rader som är på väg att kastas bort.