--- title: 'Sıralama Algoritması Seçimi' source: 'https://academia.sh/tr/kurslar/algoritmalar/siralama-algoritmasi-secimi' course: Algoritmalar language: tr updated: '2026-08-17T18:07:41+00:00' license: 'CC BY-SA 4.0' --- # Sıralama Algoritması Seçimi Veri özelliklerine göre karar tablosu, çok anahtarlı sıralamada kararlılığın kullanımı, karma gerçekleştirimler ve sıralamanın gereksiz olduğu durumlar. 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. ```python 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.