--- title: 'Karşılaştırmasız Sıralamalar' source: 'https://academia.sh/tr/kurslar/algoritmalar/karsilastirmasiz-siralamalar' course: Algoritmalar language: tr updated: '2026-08-17T18:07:44+00:00' license: 'CC BY-SA 4.0' --- # Karşılaştırmasız Sıralamalar Karşılaştırmalı sıralamanın karar ağacı alt sınırı; sayma, kova ve taban sıralamasının varsayımları, maliyetleri ve sınırları. Üç 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}$. ```python 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. ```python 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. ```python 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. ```python 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.