Sıralama ve arama algoritmaları

Geçen dersin diliyle konuşmanın tam zamanı: kabarcık ve seçmeli sıralama neden O(n²), birleştirme ve hızlı sıralama neden O(n log n), ikili arama neden O(log n)? Yazılı sınav "dizinin bir tur sonraki hâlini" sormayı sever; mülakat merge/quick karşılaştırmasını. Üretimdeki karşılığı ise şudur: kendi sıralamanı asla yazmazsın — ama Array.Sort ile LINQ OrderBy'ın farkını bilmediğinde eşit elemanların sırası sessizce karışır.

01Ne öğreneceksin

02Sıralama neden bu kadar merkezî?

Sıralı veri, iki süper güç verir: ikili arama yapılabilir (O(n) → O(log n) — dersin finalinde) ve komşuluk anlamlı hâle gelir (en yakın değer, aralık sorgusu, tekrarları yan yana görme, iki listeyi birleştirme). İnsan gözü de sıralı listeyi tarar — raporların, tabloların, log dosyalarının sıralanmasının nedeni. Bu yüzden "önce sırala" birçok problemin ilk adımıdır ve veritabanı indeksinden (9. dersin B-ağacı) Excel'in sütun okuna kadar her yerde bir sıralama yatar.

Bu derste dört algoritma göreceksin; ikisi öğretici (kabarcık, seçmeli), ikisi gerçek dünyanın işçisi (merge, quick). Bir teori notu — sorulursa cevabı bil: elemanları yalnızca karşılaştırarak sıralayan hiçbir algoritma O(n log n)'den hızlı olamaz; bu kanıtlanmış bir alt sınırdır. Merge ve quick bu sınıra dayanır — "daha iyisi" aranmaz, sabitler ve bellek üzerinde oynanır.

03Öğretici ikili: kabarcık ve seçmeli

Kabarcık (bubble) sıralama: komşu çiftleri karşılaştır, yanlış sıradaysa takas et; dizinin sonuna kadar süpür. Her turun sonunda en büyük eleman en sona "kabarcık gibi yükselmiş" olur — sınavın "bir tur sonrası" sorusu tam bunu yoklar:

[5, 3, 8, 2]  1. tur:
5-3 karşılaştır → takas → [3, 5, 8, 2]
5-8 karşılaştır → yerinde → [3, 5, 8, 2]
8-2 karşılaştır → takas → [3, 5, 2, 8]   ← tur bitti: 8 SONDA
2. tur → [3, 2, 5, 8] · 3. tur → [2, 3, 5, 8]

Seçmeli (selection) sıralama: ters strateji — kalanların en küçüğünü bul, başa koy; sınırı bir ilerlet, tekrarla. Her turda bir eleman kesin yerine oturur; turdaki iş "tarayıp minimum seçmek"tir ve takas tur başına en fazla birdir (kabarcıktan ayırt edici farkı). İkisi de iç içe iki döngüdür → geçen dersin deseniyle O(n²); 100.000 elemanda 10 milyar karşılaştırma — pratik dışı. Öğretici değerleri, "sıralama nedir"i elle hissettirmeleri ve sınavlarda izleme/karşılaştırma sorusu olmalarıdır. Aileden bir üçüncüyü isim düzeyinde tanı: eklemeli (insertion) sıralama — eldeki kartı sıralı kısma sokar; o da O(n²)'dir ama neredeyse sıralı veride O(n)'e yaklaşır; kütüphanelerin küçük parçalarda ona dönmesinin nedeni bu.

04Birleştirme sıralaması: böl, sırala, birleştir

Merge sort, "böl ve yönet" stratejisinin (12. derste genelleşecek) ders kitabı örneğidir: diziyi ikiye böl, iki yarıyı (özyinelemeyle) sırala, sonra iki sıralı diziyi tek geçişte birleştir — iki desteyi üstten karşılaştıra karşılaştıra tek deste yapmak gibi:

[8, 3, 5, 2, 9, 1]
böl:        [8, 3, 5]        [2, 9, 1]
böl+sırala: [3, 5, 8]        [1, 2, 9]
birleştir:  3<1? hayır→1 · 3<2? hayır→2 · 3→ · 5<9→5 · 8<9→8 · 9
sonuç:      [1, 2, 3, 5, 8, 9]

Maliyet: log n bölme seviyesi × her seviyede n'lik birleştirme işi = O(n log n) — her durumda, garantili. Girdi ne olursa olsun süre değişmez; bu öngörülebilirlik, merge'ün imzasıdır. Bedeli bellek: birleştirme için O(n) ek dizi gerekir (yerinde değildir). İkinci imzası kararlılıktır (stable): eşit elemanların girişteki göreli sırası korunur. Neden önemli? Kayıtları önce ada göre, sonra şehre göre sıralarsan; kararlı algoritmada her şehrin içi ada göre sıralı kalır — raporlama ve çok anahtarlı sıralamanın temeli. Bu kavram birazdan C# tarafında gerçek bir tuzağa dönüşecek.

05Hızlı sıralama: pivotun kumarı

Quicksort da böl-yönet'tir ama bölmeyi değere göre yapar: bir pivot seç; diziyi "pivottan küçükler | pivot | büyükler" diye yeniden dizle (bölümleme/partition — tek geçiş, yerinde); sonra iki tarafı özyinelemeyle sırala. Birleştirme adımı yoktur — bölümleme bittiğinde pivot kesin yerindedir:

[8, 3, 5, 2, 9, 1]  pivot=5
bölümle:  [3, 2, 1]  5  [8, 9]
özyinele:  [1, 2, 3]  5  [8, 9]  →  [1, 2, 3, 5, 8, 9]

Pivot her turda diziyi kabaca ortadan bölerse seviye sayısı log n olur → ortalama O(n log n); üstelik yerinde çalışır ve iç döngüsü ardışık bellek taradığı için önbellek dostudur (2. ders) — pratikte merge'den de hızlıdır, adı buradan gelir. Kumar en kötü durumdadır: pivot hep en küçük/büyük düşerse bölme 1'e n−1 olur → O(n²). Naif "ilk elemanı pivot seç" uygulamasında bu, tam da zaten sıralı dizide başa gelir — 9. dersin BST dengesizliğiyle aynı ironi: en masum girdi, en kötü durum. Modern kütüphaneler pivotu akıllı seçer (medyan/rastgele) ve derinlik kaçarsa heapsort'a geçer (heap — 9. ders; bu karma stratejinin adı introsort'tur) — n² riski pratikte kapatılmıştır.

Karşılaştırma tablosu — mülakatın klasiği:

(*özyineleme yığını.) Seçim ilkesi: öngörülebilirlik ve kararlılık istiyorsan merge; ortalama hız ve az bellek istiyorsan quick; pratikte ikisinin karmasını kütüphane senin için seçer.

06İkili arama: sıralılığın ödülü

Sırasız dizide arama tek yoldur: baştan sona bak — doğrusal arama, O(n). Dizi sıralıysa oyun değişir: ortaya bak; aradığın küçükse sol yarıya, büyükse sağ yarıya in; tekrarla. Her adım aday kümesini yarılar → O(log n):

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]   hedef: 23
orta=16 → 23>16 → sağ yarı [23, 38, 56, 72, 91]
orta=56 → 23<56 → sol yarı [23, 38]
orta=23 → BULUNDU — 10 elemanda 3 adım (1 milyonda ~20, 1 milyarda ~30)

İki şartı vardır: veri sıralı olmalı ve ortaya O(1)'de atlanabilmeli — yani dizi/List (8. ders: adres aritmetiği); bağlı listede ikili arama anlamsızdır, ortayı bulmak zaten O(n)'dir. Ne zaman değer? Hesap basit: sıralama O(n log n) yatırımdır; bir kez sıralayıp çok kez arayacaksan anında amorti eder; tek arama içinse doğrusal tarama daha ucuzdur. Üçüncü seçeneği de hatırla (9. ders): aramaların anahtar eşitliğiyse Dictionary O(1) verir; ikili aramanın sahası "sıralı düzende aralık/komşuluk da lazım" olan durumlardır. C#'ta hazırdır: Array.BinarySearch / List.BinarySearch — bulunamayınca negatif değer döndürür (eklenecek konumu kodlar); elle yazarken ise klasik tuzak orta = (sol + sag) / 2'nin çok büyük dizilerde int taşmasıdır (1. ders!) — güvenlisi sol + (sag - sol) / 2.

07Gerçek dünya: kütüphane sıralamaları ve kararlılık tuzağı

Üretim kuralı nettir: sıralama algoritmasını kendin yazmazsın — kütüphane sürümü yıllarca optimize edilmiştir. Senin işin iki şeydir: neye göre sıralanacağını söylemek ve hangi aracın hangi garantiyi verdiğini bilmek:

• Array.Sort / List.Sort: yerinde, introsort (quick + heap + küçük parçada insertion — bu dersin üç algoritması tek araçta!). Kararlı DEĞİLDİR.
• LINQ OrderBy(...) (Hat 03'te ayrıntısı): yeni sıralı dizi üretir, kararlıdır; ikincil anahtar ThenBy ile zincirlenir.

Tuzak gerçek: personel listesini önce ada göre sıraladın; sonra list.Sort((a, b) => a.Sehir.CompareTo(b.Sehir)) ile şehre göre sıraladın — aynı şehirdeki kişilerin ad sırası bozulabilir, üstelik her çalıştırmada farklı biçimde. OrderBy(p => p.Sehir).ThenBy(p => p.Ad) ise hem niyeti açık yazar hem kararlılık garantisi verir. "Rapordaki sıra ara sıra karışıyor" ticket'ının klasik köküdür. "Neye göre" sorusunun altyapısını da tanıyorsun: IComparable (Hat 1 yeterlilik projesinde kullandın) tipin doğal sırasını tanımlar; Comparison/IComparer duruma özel sırayı verir. Son bir ufuk notu: karşılaştırma yapmayan sıralamalar da vardır — sayma/kova/radix sort, "değerler dar aralıkta tamsayı" gibi özel koşullarda O(n)'e iner; n log n alt sınırı yalnız karşılaştırma tabanlılar içindir. İsimlerini bilmen yeter.

08Mini alıştırma — Yaz, yarıştır, yakala

09Kendini sına

Kabarcık ile seçmeli sıralamanın stratejilerini ayırt et; bir turun sonunda her birinde ne garanti edilir?

Kabarcık komşuları karşılaştırıp takas eder; turun sonunda en büyük eleman dizinin sonuna oturur (her turda çok sayıda takas olabilir). Seçmeli, kalanların en küçüğünü bulup başa koyar; turun sonunda en küçük eleman kesin yerindedir ve tur başına en fazla bir takas yapılır. İkisi de iç içe iki döngüyle O(n²)'dir; pratik kullanımları yoktur, sınav izleme sorularının klasiğidir.

Merge sort ile quicksort'u en kötü durum, bellek ve kararlılık açısından karşılaştır; kütüphaneler pratikte ne yapar?

Merge: her durumda O(n log n) garantili, O(n) ek bellek, kararlı — öngörülebilirliğin algoritması. Quick: ortalama O(n log n) ve yerinde, önbellek dostu olduğundan pratikte en hızlısı; ama kötü pivotta O(n²) (naif uygulamada sıralı girdi tetikler) ve kararsız. Kütüphaneler karma kullanır: .NET Array.Sort introsort'tur — quick ile başlar, derinlik kaçarsa heapsort'a geçer, küçük parçalarda insertion'a döner; n² riski pratikte kapalıdır.

İkili aramanın iki ön şartı nedir? 1 milyon elemanda kaç karşılaştırma yapar ve "önce sırala sonra ara" ne zaman mantıklıdır?

Şartlar: veri sıralı olmalı ve ortadaki elemana O(1)'de erişilebilmeli (dizi/List; bağlı listede anlamsız). Her adım aday kümesini yarılar: 1 milyonda ~20, 1 milyarda ~30 karşılaştırma. Sıralama O(n log n) yatırımdır: bir kez sıralayıp çok kez arayacaksan amorti eder; tek arama için doğrusal tarama daha ucuzdur. Anahtar eşitliği aramalarında ise Dictionary O(1) ile daha da iyidir — ikili aramanın sahası sıralı düzen + aralık/komşuluk gereken işlerdir.

Kararlı sıralama nedir? C#'ta hangi araç kararlıdır ve bunun pratikte yarattığı fark nedir?

Eşit anahtarlı elemanların girişteki göreli sırasını koruyan sıralamadır. C#'ta LINQ OrderBy/ThenBy kararlıdır; Array.Sort/List.Sort (introsort) kararlı değildir. Fark çok anahtarlı sıralamada görünür: ada göre sıralı listeyi şehre göre Sort ile sıralarsan şehir içi ad sırası bozulabilir; OrderBy(Sehir).ThenBy(Ad) hem korur hem niyeti açıkça yazar. "Rapor sırası ara sıra karışıyor" hatasının tipik nedeni budur.

10Sınav köşesi