Sıralama Algoritmaları: Bilgisayar Biliminin En Temel Yarışması (Quick Sort, Merge Sort)

Bir oyun kartı destesini karıştırıp sıraya dizmek için kaç tane karşılaştırma yaparsınız? 10 kart için kolay; 100 kart için biraz uğraşır; 10000 kart için saatler alır. Bir milyar kart için? Yıllar.

Ama doğru algoritma seçerseniz, bir milyar kartı bir saniyenin altında sıralayabilirsiniz.

Bu, modern bilgisayar biliminin "sıralama problemi"dir. Görünüşte sade — "büyükten küçüğe diz" — ama içindeki matematik son derece zengindir. Quick Sort, Merge Sort, Bubble Sort, Heap Sort gibi klasik algoritmalar, bilgisayar bilimi öğretiminin temel konusudur. Her birinin matematiksel performans karakteristiği farklıdır; doğru olanı seçmek, bir uygulamanın bin kat daha hızlı çalışmasını sağlar.

Sade örnek: Bubble Sort

En basit sıralama algoritması Bubble Sort (Kabarcık Sıralaması). Listenizdeki ardışık her çifte bakın; yanlış sıradalarsa yer değiştirin. Listenin sonuna ulaştığınızda baştan başlayın. Hiçbir değişim yapmadan sonuna ulaşırsanız sıralama bitmiş demektir.

Algoritma sade ama yavaştır. $n$ eleman için en kötü durumda yaklaşık $n^2$ karşılaştırma yapar. 1000 eleman için ~$10^6$ işlem; 1 milyon eleman için ~$10^{12}$ işlem (modern bir bilgisayarda yaklaşık 1000 saniye, yani 17 dakika).

Bu, kabul edilemez yavaş. Daha akıllı algoritmalar gerekli.

Büyük O notasyonu

Algoritmaların hızını büyük O notasyonu ile karşılaştırırız. Bir algoritma $O(f(n))$ ise, çalışma süresi $n$ büyük olduğunda yaklaşık $f(n)$ ile orantılıdır.

Yaygın sıralama algoritmaları için ortalama çalışma süresi:

Algoritma	En kötü	Ortalama	Bellek
Bubble Sort	$O(n^2)$	$O(n^2)$	$O(1)$
Insertion Sort	$O(n^2)$	$O(n^2)$	$O(1)$
Selection Sort	$O(n^2)$	$O(n^2)$	$O(1)$
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n)$
Quick Sort	$O(n^2)$	$O(n \log n)$	$O(\log n)$
Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(1)$
Counting Sort	$O(n+k)$	$O(n+k)$	$O(k)$

Sayısal olarak:

• $n = 1000$ için: $n^2 = 10^6$; $n \log n \approx 10^4$. Yani $n \log n$ algoritma 100 kat daha hızlı.
• $n = 10^6$ için: $n^2 = 10^{12}$; $n \log n \approx 2 \times 10^7$. Yani 50000 kat daha hızlı.

Bu, modern bilgisayar bilimi öğretiminin en önemli derslerinden: algoritma seçimi, donanım hızından çok daha önemlidir.

Merge Sort: Böl ve Yönet

Merge Sort (Birleştirme Sıralaması), klasik bir böl ve yönet algoritmasıdır. 1945'te John von Neumann tarafından önerildi.

Mantığı sadedir:

1. Listeyi iki eşit yarıya böl.
2. Her yarıyı özyinelemeli olarak Merge Sort ile sırala.
3. İki sıralı yarıyı birleştir (her seferinde küçük olanı al).

Birleştirme adımı $O(n)$; özyineleme $\log_2 n$ seviye derinde. Toplam: $O(n \log n)$.

Avantajları:

• Çok kararlıdır: en kötü durum bile $O(n \log n)$.
• Paralleştirilebilir: iki yarıyı bağımsız işlemcilerde sırasıyla çalıştırabilirsin.

Dezavantajı:

• Ekstra bellek gerektirir ($O(n)$).

Bugün modern yazılım kütüphanelerinin pek çoğunda Merge Sort varyantları kullanılır (özellikle Java'nın Arrays.sort() metodunda, harici sıralama için).

Quick Sort: Pivot Strateji

Quick Sort (Hızlı Sıralama), 1961'de İngiliz bilgisayar bilimci Tony Hoare tarafından önerildi. O dönem Cambridge'de doktora yapmaktayken, Rusça-İngilizce makine çevirisi sözlüğünü sıralamak için yazdı.

Mantığı:

1. Bir pivot eleman seç (genellikle listedeki ortanca eleman).
2. Listeyi iki bölümle ayır: pivot'tan küçük olanlar sola, büyük olanlar sağa.
3. Her bölümü özyinelemeli olarak Quick Sort ile sırala.

Quick Sort'un ilginç bir özelliği vardır: ortalama çalışma süresi $O(n \log n)$; ama en kötü durumda (örneğin liste zaten sıralıysa ve pivot olarak ilk eleman seçilirse) $O(n^2)$'ye düşer. Modern uygulamalar bu sorunu çözmek için rastgele pivot seçimi ya da medyan-of-three gibi stratejileri kullanır.

Pratikte Quick Sort, çoğu durumda en hızlı sıralama algoritmasıdır. Modern yazılım kütüphanelerinde — Python'un sorted(), C'nin qsort(), JavaScript'in Array.prototype.sort() gibi — Quick Sort tabanlı yaklaşımlar yaygındır.

Hoare bu çalışmasıyla 1980 Turing Ödülü kazandı.

Heap Sort

Heap Sort, bir başka $O(n \log n)$ algoritma. Yığın (heap) veri yapısını kullanır.

1. Listeyi bir "max-heap"e dönüştür (en büyük eleman yukarıda).
2. En büyüğü al; listenin sonuna koy.
3. Geri kalanı yeniden "max-heap"e dönüştür.
4. Tekrarla.

Avantajı: ekstra bellek gerektirmez ($O(1)$). Dezavantajı: pratikte Quick Sort'tan biraz yavaştır.

Alt sınır: $\Omega(n \log n)$

Karşılaştırma tabanlı tüm sıralama algoritmaları için, matematiksel olarak kanıtlanmış bir alt sınır vardır:

$\text{Sıralama} \ge \Omega(n \log n)$

Yani karşılaştırma yaparak çalışan hiçbir sıralama algoritması $O(n \log n)$'den daha hızlı olamaz. Bu, Stirling formülü kullanılarak kanıtlanır: $n$ farklı elemanın olası $n!$ permütasyonu vardır; her bir karşılaştırma 1 bit bilgi verir; $n!$'i ayırt etmek için $\log_2(n!) \approx n \log n$ bit gerekir.

Bu alt sınır, sıralama probleminin matematiksel "dibi"dir. Daha hızlı olabilmek için karşılaştırma yapmamak (örneğin sayı aralığını biliyorsanız Counting Sort gibi alternatifler) gerekir.

Counting Sort ve özel durumlar

Eğer bilgi varsa (örneğin tüm sayıların 0-100 arasında olduğunu biliyorsanız), klasik karşılaştırma alt sınırını atlayabilirsiniz:

• Counting Sort: $O(n + k)$ — burada $k$ olası değer aralığı. Sayıları doğrudan sayar.
• Radix Sort: $O(d \cdot n)$ — burada $d$ basamak sayısı. Banka kart numarası gibi sabit basamaklı sayılarda kullanışlı.
• Bucket Sort: $O(n)$ — düzgün dağılmış veriler için.

Pratikte modern kütüphane sıralayıcıları (Python's TimSort, Java'nın yeni Arrays.sort()'u) hibrit yaklaşım kullanır: küçük listelerde Insertion Sort, büyük listelerde Merge Sort/Quick Sort.

TimSort: Python'un Sıralama Algoritması

2002'de Python topluluğunun üyesi Tim Peters, Python için yeni bir sıralama algoritması tasarladı: TimSort. Bu, Merge Sort + Insertion Sort hibritidir.

TimSort'un ana fikri: gerçek dünya verileri çoğu zaman kısmen sıralıdır. TimSort, listede zaten sıralı olan "run" denilen segmentleri keşfeder ve onları akıllıca birleştirir.

Bugün Python'un sorted(), Java'nın 7. sürümden sonraki Arrays.sort() (object türleri için), Android'in standart sıralayıcısı, hepsi TimSort tabanlıdır.

Pratik karşılaştırma

100 milyon eleman sıralamak için tipik modern bir bilgisayarda yaklaşık süreler:

• Bubble Sort: ~10 yıl (yapma!).
• Insertion Sort: ~5 yıl.
• Quick Sort: ~10 saniye.
• Merge Sort: ~15 saniye.
• TimSort (kısmen sıralı veriler için): ~5 saniye.
• Counting Sort (eğer aralık 0-100 ise): ~1 saniye.

Doğru algoritma seçimi, gerçekten "bir saniye vs. on yıl" farkını yaratabilir.

Modern uygulamalar

Sıralama, modern dijital dünyanın her köşesinde çalışır:

• Veritabanları — SQL sorgu sonuçlarını sıralamak.
• Arama motorları — sonuçları alaka skoruna göre sıralamak.
• Dosya sistemleri — dosyaları tarihe, boyuta, ada göre sıralamak.
• Görüntü işleme — pikselleri renge göre sıralamak (örneğin median filtre).
• Veri bilimi — analiz için verileri sıralamak.
• Grafik motorları — 3D sahnedeki nesneleri uzaklığa göre sıralamak (Z-buffer).
• Borsa sistemleri — emirleri fiyat-zaman önceliğine göre sıralamak.

Modern bir akıllı telefon, bir gün içinde trilyonlarca sıralama işlemi yapar (mostly Quick Sort + TimSort).

Bir hayat dersi

Sıralama algoritmaları, "aynı problemi farklı yöntemlerle çözmek bin kat farklı sonuçlar verebilir" gerçeğinin matematiksel olarak en açık örneklerinden biridir. Aynı bilgisayar, aynı veri, sadece algoritma değişikliği ile saniye-yıl farkı yapabilir.

Daha geniş bir hayat dersi: bilgi, çoğu zaman doğru aracın seçimi kadar değerlidir. Hangi aracı kullanacağınızı bilmek, çoğu zaman ham zekâdan daha güçlüdür.

Bir sonraki sefer cep telefonunuzda bir liste sıralandığında, bir e-posta klasörü tarihe göre düzenlendiğinde, ya da bir Google araması sonuç verdiğinde — perde arkasında 1945'te John von Neumann ya da 1961'de Tony Hoare'in yazdığı bir algoritmanın hızla çalıştığını hatırlayabilirsiniz. Sıralama, modern bilgisayar biliminin sessiz çalışan kalbidir.