Counting, radix ve bucket sort

Karşılaştırma tabanlı sıralama karar ağacı n! olası permütasyonu ayırmalıdır; worst-case Ω(n log n) karşılaştırma alt sınırı buradan gelir. Counting sort bu modeli değiştirdiği için sınırı ihlal etmez: anahtarları sınırlı tamsayı aralığına indeksler.

Counting sort frekans sayıp prefix konumlarıyla kayıtları yerleştirir. Basit değer çoğaltma sürümü tam kayıtların stabilitesini göstermez. LSD radix sort en düşük anlamlı basamaktan başlayıp her basamakta stabil bir sıralama yapar. Stabilite olmazsa önceki basamak düzeni kaybolur. Negatif sayılar, değişken uzunluk ve Unicode collation için dönüşüm/sözleşme gerekir.

Bucket sort aralığı bölgelere ayırır; iyi dağılımda hızlı olabilir ama bütün girdinin tek bucket'a düşmesi performansı bozar. Anahtar aralığı çok büyükken k boyutlu counting tamponu ayırmak kötü tercihtir. n küçük, k milyarlar ise n log n sıralama daha pratik olabilir.

def counting_sort(a, k):
    counts = [0]*k
    for x in a:
        if not 0 <= x < k: raise ValueError("out of range")
        counts[x] += 1
    return [x for x, count in enumerate(counts) for _ in range(count)]
assert counting_sort([2,0,2,1], 3) == [0,1,2,2]