Sıralama Algoritması Seçimi

Yedi algoritma ve altı ayrı ölçüt birikti. Bu ders onları tek bir karar çerçevesinde toplar. Amaç bir sıralama listesi ezberlemek değil; eldeki verinin hangi özelliğinin seçimi belirlediğini görmektir.

Ölçütlerin Toplu Görünümü

Algoritma	En kötü	Ortalama	Ek alan	Kararlı	Uyarlanabilir
Eklemeli	$O(n^2)$	$O(n^2)$	$O(1)$	Evet	Evet
Seçmeli	$O(n^2)$	$O(n^2)$	$O(1)$	Hayır	Hayır
Kabarcık	$O(n^2)$	$O(n^2)$	$O(1)$	Evet	Evet
Birleştirmeli	$O(n \log n)$	$O(n \log n)$	$O(n)$	Evet	Değişkeye bağlı
Hızlı	$O(n^2)$	$O(n \log n)$	$O(\log n)$	Hayır	Hayır
Yığın	$O(n \log n)$	$O(n \log n)$	$O(1)$	Hayır	Hayır
Sayma	$O(n + k)$	$O(n + k)$	$O(n + k)$	Evet	Hayır
Taban	$O(d(n + b))$	$O(d(n + b))$	$O(n + b)$	Evet	Hayır

Tablo tek başına karar vermez; hangi sütunun önemli olduğunu problem belirler.

Karar Tablosu

Verinin özelliği	Uygun seçim	Gerekçe
Az sayıda eleman (onlarca)	Eklemeli	Küçük sabit, basit kod
Neredeyse sıralı	Eklemeli veya koşu tabanlı birleştirmeli	Ters çift sayısı küçük
Kararlılık zorunlu	Birleştirmeli, sayma, taban	Tanım gereği kararlı
Bellek çok kısıtlı	Yığın	Ek alan $O(1)$, güvence var
En kötü durum güvencesi gerekli	Yığın veya birleştirmeli	Karesel duruma düşmez
Genel amaçlı, dizi üzerinde	Karma (hızlı + yığın + eklemeli)	Pratik hız ve güvence
Bağlı liste	Birleştirmeli	Ardışık erişim yeterli
Belleğe sığmayan veri	Dış birleştirmeli	Akış hâlinde okuma
Anahtarlar küçük tam sayı	Sayma	$O(n + k)$, karşılaştırmasız
Sabit genişlikli anahtar, çok kayıt	Taban	Basamak başına doğrusal
Çok fazla yinelenen anahtar	Üç yollu hızlı	Eşitler bölgesi tekrar işlenmez
Yalnızca en büyük $k$ eleman	$k$ boyutlu yığın	$O(n \log k)$, sıralama gerekmez

Satırların çoğu birbirini dışlamaz; birden çok koşul sağlanıyorsa daha kısıtlayıcı olan belirleyicidir. “Kararlılık zorunlu” ile “bellek kısıtlı” çakışırsa, kararlı ve yerinde bir algoritma aranır — bu ikisini birden veren gerçekleştirimler vardır, ancak sabitleri büyüktür.

Karma Gerçekleştirimler

Genel amaçlı kütüphane sıralamaları tek bir algoritma kullanmaz. İki yaygın tasarım vardır ve ikisi de bu bölümün derslerinden derlenmiştir.

Bölümleme temelli karma. Hızlı sıralamayla başlanır. Özyineleme derinliği $c \log n$ eşiğini aşarsa — yani bölmeler sürekli dengesizse — yığın sıralamasına geçilir. Belirli bir boyutun altındaki parçalar eklemeli sıralamaya bırakılır. Sonuç: hızlı sıralamanın pratik hızı, yığın sıralamasının en kötü durum güvencesi, eklemeli sıralamanın küçük sabiti.

Koşu temelli karma. Girdide zaten sıralı olan koşular bulunur, kısa koşular eklemeli sıralamayla uzatılır, ardından koşular birleştirilir. Neredeyse sıralı veride doğrusala yaklaşır, kararlıdır ve en kötü durumda $O(n \log n)$ kalır. Karşılığında ek alan ister.

Ortak ders: gerçek gerçekleştirimler, tek bir algoritmanın en iyisi olduğu iddiasında değildir; her algoritmayı en iyi olduğu bölgede kullanırlar.

Çok Anahtarlı Sıralama

Kararlılığın en yaygın kullanımı, birden çok ölçüte göre sıralamadır. İki yol vardır.

Bileşik anahtar. Karşılaştırma işlevi, ölçütleri sırayla değerlendirir. Tek geçişte biter ve kararlılık gerektirmez.

Ardışık kararlı sıralamalar. Önce ikincil ölçüte, sonra birincil ölçüte göre sıralanır. İkinci sıralama kararlı olduğu için, birincil ölçütte eşit olanların ikincil sırası korunur.

kayitlar = [
    ("Ankara", 3), ("İzmir", 1), ("Ankara", 1),
    ("Bursa", 2), ("İzmir", 3), ("Ankara", 2),
]

# İkincil ölçüt (sayı) önce, birincil ölçüt (şehir) sonra
adim1 = sorted(kayitlar, key=lambda k: k[1])
adim2 = sorted(adim1, key=lambda k: k[0])
print(adim2)
# [('Ankara', 1), ('Ankara', 2), ('Ankara', 3), ('Bursa', 2), ('İzmir', 1), ('İzmir', 3)]

# Bileşik anahtarla tek geçiş — aynı sonuç
print(sorted(kayitlar, key=lambda k: (k[0], k[1])) == adim2)     # True

İki yol aynı sonucu verir. Ardışık yöntem, ölçütlerin çalışma anında belirlendiği durumlarda (kullanıcının seçtiği sütuna göre sıralanan bir tablo) daha esnektir; bileşik anahtar ise tek geçiş olduğu için ucuzdur.

Taban sıralamasının basamak basamak çalışması da aynı ilkedir: her basamak bir ölçüttür ve kararlılık, önceki ölçütlerin sonucunu korur.

Karşılaştırma Maliyeti

Asimptotik tablolar karşılaştırmayı sabit sayar. Anahtar karmaşıksa bu varsayım bozulur: uzun metinlerin karşılaştırılması metin uzunluğuyla orantılıdır ve dile duyarlı sıralama kuralları çok daha pahalıdır.

İki sonuç doğar. Birincisi, karşılaştırma pahalıysa karşılaştırma sayısını azaltan algoritma (birleştirmeli) tercih edilir; taşıma pahalıysa taşımayı azaltan (seçmeli). İkincisi, pahalı anahtar dönüşümü sıralamadan önce bir kez yapılıp saklanabilir — sıralama boyunca her karşılaştırmada yeniden hesaplanmaz. Bu, Zaman ve Alan Ödünleşimi dersindeki önhesaplama kalıbının doğrudan uygulanışıdır.

Sıralamanın Gereksiz Olduğu Durumlar

Sıralama, ihtiyaç duyulandan fazlasını yapan bir işlemdir ve sık sık gereksiz yere çağrılır.

İhtiyaç	Sıralama yerine	Maliyet
En büyük veya en küçük eleman	Tek geçişte tarama	$O(n)$
k’ıncı en küçük eleman	Hızlı seçme	Beklenen $O(n)$
En büyük $k$ eleman	$k$ boyutlu yığın	$O(n \log k)$
Bir değerin varlığı	Karma tablosu	Beklenen $O(1)$
Yinelenenleri ayıklamak	Karma kümesi	Beklenen $O(n)$
Ortanca değeri	Seçme algoritması	Beklenen $O(n)$

Sıralamanın kendisi gerekliyse — çıktının sıralı sunulması, ikili aramaya hazırlık, çok sorgulu kullanım — maliyeti yerindedir. Tek bir soruya yanıt için sıralamak, $O(n \log n)$ ödeyip $O(n)$’lik bir iş yapmaktır.

Ölçmeden Karar Verilmeyen Nokta

Asimptotik çözümleme sınıfı belirler; sınıf içi seçim ölçüm ister. İki algoritma da $O(n \log n)$ ise fark sabittedir ve sabit; bellek erişim düzenine, anahtar tipine, veri büyüklüğüne ve gerçekleştirime bağlıdır.

Ölçüm yapılırken üç kural geçerlidir: gerçek veriyle ölçülmeli (rastgele veri, gerçek verinin kısmi sıralılığını taşımaz), girdi büyüklüğü değiştirilerek ölçülmeli (tek boyutta ölçüm sınıfı göstermez), ve ölçülen sürelerin girdiyle nasıl ölçeklendiğine bakılmalıdır — Karmaşıklık Sınıflarını Okumak dersindeki ölçek büyütme tablosu bu iş içindir.

Özet

• Seçim, algoritmanın kendisinden değil verinin özelliklerinden çıkar: boyut, kısmi sıralılık, yinelenen anahtar oranı, anahtar yapısı, bellek kısıdı ve kararlılık gereksinimi.
• Genel amaçlı gerçekleştirimler karmadır; her algoritmayı en iyi olduğu bölgede kullanır.
• Çok anahtarlı sıralama, ardışık kararlı sıralamalarla veya bileşik anahtarla yapılır.
• Karşılaştırma pahalıysa karşılaştırma sayısını, taşıma pahalıysa taşıma sayısını azaltan algoritma seçilir.
• En küçük, k’ıncı, ilk $k$ veya varlık sorularında sıralama gereksizdir; doğrusal veya beklenen sabit maliyetli çözümler vardır.
• Sınıf içi karar ölçümle verilir; ölçüm gerçek veriyle ve birden çok girdi boyutunda yapılır.

Sonraki Adım

Arama ve sıralama, tek boyutlu veriler üzerinde çalıştı: elemanlar arasında yalnızca sıra ilişkisi vardı. Sonraki konu, elemanlar arasında bağlantı olan verilere geçer. Veri Yapıları kursunda çizgeler tanımlanmış, enine ve derine arama kurulmuştu; şimdi ağırlıklı çizgelerde en kısa yol, en ucuz kapsayan ağaç ve en büyük akış problemleri ele alınacak.