Bir listeyi sürprizsiz sıralamak ve yinelenenleri ayıklamak

Sıralamak ve yinelenenleri ayıklamak, bir listeye yapabileceğiniz en basit iki iş gibi görünür; sonuçların bu kadar sık ve sessizce yanlış çıkmasının nedeni de budur. İkisi de bir karşılaştırmaya dayanır ve iki satırı neyin eşit kıldığının ya da bir satırın neden önce geldiğinin tek bir cevabı yoktur.

Sözlük sırası, sayısal sıra değildir

Metin için varsayılan karşılaştırma iki dizede birer karakter ilerler, kod noktalarını karşılaştırır ve ilk farkta durur. İçinde sayının ne olduğunu bilen hiçbir şey yoktur.

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

img10.png ikinci sıraya düşer, çünkü dördüncü karakterde 1 (U+0031) değeri 2 (U+0032) değerinden küçüktür ve karşılaştırma orada biter. Aynı kural 1.10 sürümünü 1.9 sürümünün önüne koyar ve bir ekran görüntüsü klasörünü çekildikleri sıradan başka bir sırayla listeler.

Sayısal karşılaştırma negatifleri de düzeltir: sözlük sırasında -10, -1 ile -2 arasına düşer, çünkü eksi işareti de kod noktası olan başka bir karakterden ibarettir.

Büyük harfler küçüklerden önce ve diğer kod noktası sürprizleri

ASCII'de büyük harfler 65 ile 90, küçük harfler 97 ile 122 arasını kaplar, dolayısıyla her büyük harf her küçük harften önce sıralanır.

Rakamlar bütün harflerin altında, boşluk (32) yazdırılabilir her karakterin altında, boş satır ise onun da altında durur; dolayısıyla artan bir sıralama boş ve başında boşluk olan satırları en tepede toplar, azalan bir sıralama da en altta toplar.

Satır sonundaki boşluk aynı sorunun görünmez halidir: apple ile apple yan yana sıralanır ve kaldırılmayı reddeden bir yinelenen gibi görünür. Bölünmez boşluk (U+00A0) daha kötüsüdür; normal bir boşlukla birebir aynı çizilir ama her harften sonra sıralanır. Bir Windows dosyası yalnızca satır sonlarından bölündüğünde geride kalan satır başı da öyledir. İki satır birebir aynı görünüyor ve yine de birleşmiyorsa gizli karakterlere bakın.

Aynı liste iki ülkede farklı sıralanır

Kod noktası sırası ayrıca her aksanlı karakteri her aksansız karakterden sonraya koyar. Zürich, Zzz sözcüğünden sonra; Ärger ise zebra sözcüğünden sonra sıralanır. Hiçbir dil kendi alfabesini böyle sıralamaz. Yerel ayara duyarlı harmanlama bunun yerine dil kurallarına göre karşılaştırır ve o kurallar birbiriyle anlaşamaz.

JavaScript'te bu iş Intl.Collator içinde yaşar:

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

Aynı nesne daha önceki sorunları da kapsar. { numeric: true } seçeneği rakam dizilerini sayı olarak karşılaştırır ki bu doğal sıradır; sensitivity ise neyin fark sayılacağını belirler: "base" harf durumunu ve aksanları yok sayar, "accent" yalnızca harf durumunu, "case" ise yalnızca aksanları yok sayar. Yerel ayarı yazmamak makinede ne ayarlıysa onu kullanmak demektir; aynı kodun iki dizüstünde iki farklı sıra döndürmesi de böyle olur. Çıktının her yerde aynı olması gerektiğinde yerel ayarı açıkça yazın.

Hangi yinelenenler yinelenen sayılır

Yinelenen ayıklama, ancak arkasındaki eşitlik sınavı kadar iyi tanımlanmıştır. Hepsi de üzerinde ince aksan bulunan cafe sözcüğü olarak görünen beş satırı ele alın:

Dört makul kural dört farklı cevap verir:

Hiçbiri yanlış değildir; farklı soruları cevaplarlar. Normalleştirme göründüğünden daha önemlidir, çünkü macOS dosya adlarından gelen metin genellikle ayrışık (NFD), Windows ile web formlarından gelen metin ise birleşik (NFC) olarak varır; dolayısıyla iki kaynaktan yapıştırılan bir liste görünmez ikizler toplar. NFKC daha ileri gider ve fi bitişik harfi gibi uyumluluk karakterlerini düz karşılıklarına katlar.

Gelenek olarak ilk karşılaşılan kazanır, dolayısıyla düzensiz kopya önce yapıştırıldıysa hayatta kalan o olur. Ayrıca yinelenenleri kaldırmak, benzersiz öğeleri bulmaktan farklı bir istektir: Remove Duplicate Lines her birinden birer tane bırakır, List Frequency'deki benzersiz küme ise tam olarak bir kez geçen öğelerden oluşan daha küçük gruptur.

Kararlılık ve iki anahtara göre sıralama

Kararlı bir sıralama, karşılaştırıcının eşit saydığı girdilerin girdideki sıralarını korumasını güvence altına alır. Ard arda geçişlerle çok anahtarlı sıralamayı çalışır kılan da budur: önce en az önemli anahtara, sonra en önemlisine göre sıralayın. Önce ada, sonra departmana göre sıralamak departmanları sıraya sokar ve her birinin içinde adları sıralı bırakır. Kararsız bir sıralama, ikinci geçişi yaparken birincinin yaptığını bozar ve sonuç neredeyse doğru görünür ki bu, yanlış görünmekten daha kötüdür.

Ters çevirmenin de aynı kancası vardır, çünkü sıralı bir listeyi çevirmek eşit gruplarının her birini de tersine çevirir. Reverse List aracını, azalan bir sıralamaya kestirme olarak değil, sıranın tamamını döndürmek istediğinizde kullanın.

Uygulamalar birbirinden ayrılır. JavaScript'in Array.prototype.sort işlevinin kararlı olması ancak ES2019'dan beri zorunludur; öncesinde V8, küçük bir dizi boyutunun üstünde kararsız bir quicksort kullanıyordu, dolayısıyla aynı kod on öğede ve on binde farklı davranıyordu. Python'ın sorted işlevi kararlıdır, GNU sort ise -s verilmedikçe kararlı değildir.

Karıştırmak bir sıralama türü değildir

Tek satırlık karıştırma, list.sort(() => Math.random() - 0.5), yanlıdır. Sıralama, karşılaştırıcısının tutarlı bir düzeni tarif ettiğini varsayar ve yalnızca algoritmasının ihtiyaç duyduğu çift altkümesini sorar. Her çağrıda yeni bir sayı atan bir karşılaştırıcı bu varsayımı bozar, dolayısıyla sonuç algoritmaya ve dizinin uzunluğuna bağlı olur: öğeler başladıkları yerin yakınında kalmaya eğilimlidir ve bazı permütasyonlar diğerlerinden çok daha sık ortaya çıkar.

Doğru bir karıştırma Fisher-Yates kullanır; sondan başlayarak yürür ve her öğeyi, kendisi dahil kendinden önceki bir konumdan tekdüze seçilmiş bir öğeyle takas eder:

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

Yaygın bozuk çeşitleme, döngünün içinde Math.random() * list.length kullanarak her seferinde dizinin tamamından çeker. Bu, n üzeri n tane eşit olasılıklı çekiliş dizisi verir ki bu sayı n faktöriyel tane sıralamaya tam bölünmez, dolayısıyla bazı sıralamalar daha sık çıkar.

Rastgelelik ile sıralama doğru biçimde birleştirilebilir: her öğeye baştan tek bir rastgele anahtar verip o anahtara göre sıralayın, çünkü karşılaştırıcı böylece tutarlı kalır. Hata, zarı karşılaştırmanın içinde atmaktır.

Adımların gitmesi gereken sıra

Liste sorunlarının çoğu, doğru işlemleri yanlış sırayla yapmaktan doğar.

1. Önce sarmalı açın. Koddan kopyalanmış bir liste "apple", biçiminde gelir; tırnaklar ve virgül dizenin parçasıdır, dolayısıyla hiçbir zaman apple ile eşleşmez. Unwrap List Items bunları ayıklar.
2. Kırpın ve normalleştirin ki eşitlik sizin düşündüğünüz anlama gelsin.
3. Yinelenenleri ayıklayın, eşleştirme kuralını varsayılan olarak kabul etmek yerine bilerek seçerek.
4. Sıralayın. Sort Lines metin, sayı, uzunluk ve rastgele sırayı kapsar; aksanlı veriler için bir yerel ayar ekleyin.
5. Yeniden biçimlendirmeyi en sona bırakın. Group List Items sonucu istek başına bir sınır için sabit boyutlu yığınlara böler, Rotate List ise içerideki sırayı değiştirmeden her şeyi kaydırır.

Kırpmadan önce yinelenenleri ayıklamak geride yakın yinelenenler bırakır; yinelenenleri ayıklamadan önce sıralamak ise az sonra atılacak satırları sıralamaktan başka bir şey değildir.