Karşılaştırmasız Sıralamalar

Üç farklı fikir — birleştirme, bölümleme, yığın — aynı sınıra çıktı: $\Theta(n \log n)$. Bu bir rastlantı değildir. Bu ders önce sınırın neden aşılamadığını kanıtlar, sonra kanıtın varsayımını kaldırarak sınırın nasıl aşılabildiğini gösterir.

Alt Sınırın Kanıtı

Karşılaştırmalı bir sıralama algoritması, elemanların değerlerine değil yalnızca karşılaştırma sonuçlarına bakar. Böyle bir algoritmanın davranışı bir karar ağacı olarak çizilebilir: her iç düğüm bir karşılaştırma, her dal sonuçlardan biri, her yaprak üretilen bir permütasyondur.

Algoritma doğruysa, $n$ elemanın her olası dizilişini doğru sıralamalıdır; dolayısıyla ağaçta en az $n!$ yaprak bulunur. En kötü durum karşılaştırma sayısı ağacın yüksekliğidir ve yüksekliği $h$ olan ikili ağacın en çok $2^h$ yaprağı vardır:

$$2^h \geq n! \implies h \geq \log_2(n!) = \Omega(n \log n)$$

Son eşitlik, $n!$ çarpanlarının en az yarısının $n/2$’den büyük olmasından çıkar: $n! \geq (n/2)^{n/2}$, yani $\log_2(n!) \geq \frac{n}{2}\log_2\frac{n}{2}$.

import math

for n in (10, 100, 1_000, 10_000):
    print(n, round(math.log2(math.factorial(n))), round(n * math.log2(n)))

# 10 22 33
# 100 525 664
# 1000 8529 9966
# 10000 118458 132877

Alt sınır ile üst sınır aynı mertebededir; birleştirmeli sıralama sınırın yalnızca küçük bir çarpanı kadar uzağındadır. Karşılaştırmalı sıralamada yapılacak iyileştirme sabitle sınırlıdır.

Kanıtın dayandığı varsayım tektir: algoritma yalnızca karşılaştırma yapar. Anahtarların yapısı kullanılırsa kanıt geçersizleşir.

Sayma Sıralaması

Varsayım: anahtarlar, $0$ ile $k-1$ arasında tam sayılardır.

Her değerin kaç kez geçtiği sayılır, sayımlar birikimli toplama çevrilir ve elemanlar doğrudan son konumlarına yazılır.

def sayma_siralamasi(dizi: list[int], k: int) -> list[int]:
    """Anahtarlar 0..k-1 aralığında. Maliyet O(n + k), kararlı."""
    sayim = [0] * k
    for deger in dizi:
        sayim[deger] += 1

    for i in range(1, k):                  # birikimli toplam: bitiş konumları
        sayim[i] += sayim[i - 1]

    sonuc = [0] * len(dizi)
    for deger in reversed(dizi):           # sondan başa gitmek kararlılığı korur
        sayim[deger] -= 1
        sonuc[sayim[deger]] = deger
    return sonuc


print(sayma_siralamasi([5, 2, 9, 1, 5, 6], 10))     # [1, 2, 5, 5, 6, 9]
print(sayma_siralamasi([3, 0, 3, 0], 4))            # [0, 0, 3, 3]

Maliyet $O(n + k)$, ek alan $O(n + k)$’dir. Hiçbir karşılaştırma yapılmaz; her eleman konumunu aritmetikle bulur.

Ters yönde dolaşmak bir ayrıntı değildir: kararlılığı sağlayan tam olarak budur. Eşit anahtarlı elemanlardan sonda olan, birikimli sayacın son konumuna yerleşir ve göreli sıra korunur. Sayıların kendisinde bu görünmez; anahtarın bir kaydın parçası olduğu kullanımda belirleyicidir.

Yöntemin sınırı $k$’dedir: değer aralığı eleman sayısına göre çok büyükse ($k \gg n$), maliyet ve bellek $k$ tarafından belirlenir. Otuz iki bitlik tam sayıları sayma sıralamasıyla sıralamak dört milyar girdilik bir sayım dizisi ister.

Kova Sıralaması

Varsayım: anahtarlar bilinen bir aralıkta ve yaklaşık düzgün dağılmıştır.

Aralık eşit parçalara bölünür, her eleman kendi kovasına atılır, kovalar kendi içinde sıralanır ve sırayla birleştirilir.

def kova_siralamasi(dizi: list[float], kova_sayisi: int) -> list[float]:
    """0 <= x < 1 aralığındaki değerler için. Düzgün dağılımda beklenen maliyet O(n)."""
    if not dizi:
        return []
    kovalar: list[list[float]] = [[] for _ in range(kova_sayisi)]
    for deger in dizi:
        kovalar[int(deger * kova_sayisi)].append(deger)

    sonuc: list[float] = []
    for kova in kovalar:
        kova.sort()                        # küçük kova: eklemeli sıralama da olur
        sonuc.extend(kova)
    return sonuc


print(kova_siralamasi([0.42, 0.11, 0.95, 0.47, 0.03], 5))
# [0.03, 0.11, 0.42, 0.47, 0.95]

Düzgün dağılımda her kovaya ortalama $n / \text{kova sayısı}$ eleman düşer; kova sayısı $n$ ile orantılı seçilirse kova içi sıralamalar sabit maliyetli olur ve beklenen toplam $O(n)$ çıkar.

Varsayım bozulduğunda güvence de bozulur: tüm elemanlar tek kovaya düşerse maliyet, kova içi algoritmanın maliyetine — genellikle $O(n \log n)$ veya $O(n^2)$’ye — geriler. Bu, “doğrusal” iddiasının veriye bağlı olduğu bir örnektir.

Taban Sıralaması

Varsayım: anahtarlar sabit sayıda basamaktan oluşur.

Elemanlar basamak basamak sıralanır. En az anlamlı basamaktan başlanır ve her basamakta kararlı bir sıralama kullanılır; kararlılık, önceki basamaklarda kurulan sıranın korunmasını sağlar.

def taban_siralamasi(dizi: list[int], taban: int = 10) -> list[int]:
    """Negatif olmayan tam sayılar için. Maliyet O(d * (n + taban))."""
    if not dizi:
        return []
    sonuc = list(dizi)
    bolen = 1
    while max(sonuc) // bolen > 0:
        kovalar: list[list[int]] = [[] for _ in range(taban)]
        for deger in sonuc:
            kovalar[(deger // bolen) % taban].append(deger)
        sonuc = [deger for kova in kovalar for deger in kova]
        bolen *= taban
    return sonuc


print(taban_siralamasi([170, 45, 75, 90, 2, 802, 24, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(taban_siralamasi([5, 2, 9, 1, 5, 6]))
# [1, 2, 5, 5, 6, 9]

Basamak sayısı $d$ ve taban $b$ için maliyet $O(d \cdot (n + b))$’dir. Anahtar genişliği sabitse — sabit genişlikli tam sayılar, sabit uzunlukta metinler — bu ifade $O(n)$’e indirgenir.

En anlamlı basamaktan başlayan değişkeler de vardır; metin sıralamasında erken ayrım sağladıkları için tercih edilirler, ancak özyinelemeli bir yapı gerektirirler.

“Doğrusal” Ne Kadar Doğrusal

Üç algoritma da alt sınırı aşar, ama bedelsiz değildir. Dürüst bir değerlendirme üç noktayı kaydeder.

Varsayımlar gerçek kısıtlardır. Sayma sıralaması küçük tam sayı aralığı, kova sıralaması düzgün dağılım, taban sıralaması sabit genişlikli anahtar ister. Genel amaçlı bir kütüphane sıralaması bu varsayımları yapamaz.

Anahtar genişliği $n$’e bağlıdır. $n$ farklı anahtar birbirinden ayrılacaksa her anahtar en az $\log_2 n$ bit olmalıdır. Taban sıralamasında basamak sayısı bu yüzden $d = \Theta(\log n)$’dir ve maliyet aslında $\Theta(n \log n)$ bit işlemine karşılık gelir. Alt sınır çiğnenmez; farklı bir işlem birimi sayılmıştır.

Ek alan gerekir. Üçü de yerinde değildir; sayma ve kova sıralaması $O(n + k)$ alan kullanır.

Buna karşın koşullar sağlandığında kazanç gerçektir: milyonlarca kaydı sabit genişlikli bir kimlik alanına göre sıralamak, taban sıralamasıyla karşılaştırmalı bir algoritmadan belirgin biçimde hızlıdır.

Özet

• Karar ağacı akıl yürütmesi, karşılaştırmalı sıralamanın en kötü durumda $\Omega(n \log n)$ karşılaştırma gerektirdiğini gösterir.
• Kanıtın tek varsayımı, algoritmanın yalnızca karşılaştırma yapmasıdır; anahtar yapısı kullanılırsa sınır aşılabilir.
• Sayma sıralaması küçük tam sayı aralığında $O(n + k)$ ve kararlıdır; ters yönde dolaşmak kararlılığın koşuludur.
• Kova sıralaması düzgün dağılımda beklenen $O(n)$ verir; dağılım bozulursa güvence kaybolur.
• Taban sıralaması, her basamakta kararlı bir sıralama kullanarak $O(d(n + b))$ çalışır.
• Doğrusallık iddiaları varsayıma bağlıdır ve anahtar genişliği $n$’e bağlıysa alt sınır farklı bir birimde yeniden görünür.

Sonraki Adım

Yedi algoritma ve birbirinden farklı ölçütler birikti: en kötü durum, kararlılık, ek alan, uyarlanabilirlik, bellek erişim düzeni ve anahtar yapısı. Sonraki ders bunları tek bir karar tablosunda toplayacak ve “hangi veriye hangi algoritma” sorusunu yanıtlayacak.