--- title: 'Hızlı Sıralama' source: 'https://academia.sh/tr/kurslar/algoritmalar/hizli-siralama' course: Algoritmalar language: tr updated: '2026-08-17T18:07:45+00:00' license: 'CC BY-SA 4.0' --- # Hızlı Sıralama Bölümleme ile yerinde sıralama, pivot seçiminin ortalama ve en kötü duruma etkisi, üç yollu bölümleme ve k'ıncı elemanı seçme. Birleştirmeli sıralama işi birleştirme adımında yapıyordu: bölme ucuz, birleştirme pahalıydı. Hızlı sıralama bunu tersine çevirir — **bölme pahalı, birleştirme yoktur**. Fikir şudur: bir eleman seçilir (pivot), dizi ondan küçükler ve büyükler olarak ikiye ayrılır. Pivot artık kesin yerindedir; iki parça bağımsız sıralanır ve yan yana durdukları için ek bir işlem gerekmez. ## Bölümleme Bölümleme, pivotu son eleman seçip diziyi tek geçişte iki bölgeye ayırır. ```python def bolumle(d: list[int], bas: int, son: int) -> int: """d[bas..son] aralığını pivota göre böler, pivotun son konumunu döndürür. Değişmez: d[bas..i] pivottan küçük veya eşit, d[i+1..j-1] pivottan büyük. """ pivot = d[son] i = bas - 1 for j in range(bas, son): if d[j] <= pivot: i += 1 d[i], d[j] = d[j], d[i] d[i + 1], d[son] = d[son], d[i + 1] return i + 1 ornek = [5, 2, 9, 1, 5, 6] k = bolumle(ornek, 0, len(ornek) - 1) print(k, ornek) # 4 [5, 2, 1, 5, 6, 9] ``` Pivot değeri 6'dır; işlem sonunda 4 numaralı dizine yerleşir. Solunda ondan büyük hiçbir eleman, sağında ondan küçük hiçbir eleman kalmaz. Bölümleme $O(n)$ zaman, $O(1)$ ek alan kullanır. Bu **Lomuto** bölümlemesidir; yazımı kısadır. **Hoare** bölümlemesi iki uçtan ortaya doğru ilerler, daha az yer değiştirme yapar ve pratikte tercih edilir; karşılığında sınır koşulları daha incedir ve pivotun kesin konumunu döndürmez. ## Özyinelemeli Çatı ```python def hizli_siralama(dizi: list[int]) -> list[int]: d = list(dizi) def sirala(bas: int, son: int) -> None: if bas >= son: # taban durumu: sıfır veya tek eleman return k = bolumle(d, bas, son) sirala(bas, k - 1) sirala(k + 1, son) # pivot (k) yerinde; yeniden işlenmez sirala(0, len(d) - 1) return d print(hizli_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(hizli_siralama([]), hizli_siralama([4])) # [] [4] ``` Doğruluk tümevarımla gelir: bölümlemeden sonra pivot kesin yerindedir ve iki parça birbirinden bağımsızdır; parçalar doğru sıralanırsa tüm dizi sıralıdır. Algoritma **yerindedir** — ek alan yalnızca özyineleme yığıtıdır — ve **kararlı değildir**: uzak elemanlarla yer değiştirme, eşit anahtarlıların sırasını bozar. ## Maliyet ve Pivot Seçimi Maliyet, bölümlemenin ne kadar dengeli olduğuna bağlıdır. **Dengeli bölme.** Pivot her seferinde ortaya düşerse bağıntı $T(n) = 2T(n/2) + O(n)$ olur ve sonuç $\Theta(n \log n)$'dir. **Dengesiz bölme.** Pivot her seferinde en küçük veya en büyük eleman olursa bir parça boş kalır: $T(n) = T(n-1) + O(n)$, yani $\Theta(n^2)$. İkinci durum kuramsal değildir. Son elemanı pivot seçen yukarıdaki gerçekleştirim, **zaten sıralı** bir dizide tam olarak bu davranışı gösterir. ```python def bolumleme_sayaci(dizi: list[int]) -> int: """Bölümleme karşılaştırmalarının toplam sayısı.""" d, toplam = list(dizi), 0 def sirala(bas: int, son: int) -> None: nonlocal toplam if bas >= son: return toplam += son - bas k = bolumle(d, bas, son) sirala(bas, k - 1) sirala(k + 1, son) sirala(0, len(d) - 1) return toplam n = 500 print(bolumleme_sayaci(list(range(n)))) # 124750 — sıralı: karesel print(bolumleme_sayaci([(i * 7919) % n for i in range(n)])) # 5322 — dengeli girdi ``` Sıralı girdide karşılaştırma sayısı $n(n-1)/2$'ye tam olarak eşittir. Aynı boyuttaki dengeli girdide sayı yirmi kattan fazla düşer. Çözüm pivotu daha dikkatli seçmektir: | Seçim | En kötü durumu tetikleyen girdi | |---|---| | İlk veya son eleman | Sıralı veya ters sıralı dizi | | Ortadaki eleman | Özel olarak kurulmuş dizi | | Üçün ortancası (ilk, orta, son) | Özel olarak kurulmuş dizi | | Rastgele eleman | Yok — girdi belirlemez | İlk üçü belirlidir (deterministic); yeterince bilgili bir karşı oyuncu, algoritmayı karesele düşüren girdiyi her zaman üretebilir. Rastgele pivotta ise girdinin hangi elemanının seçileceği belli olmadığından beklenen maliyet $O(n \log n)$'dir ve bu, girdiye değil rastgeleliğe dayanır. Beklenen maliyetin doğrusal-logaritmik olmasının nedeni, bölmelerin **çoğunlukla makul** olmasıdır: rastgele bir pivot, ortadaki yarıya yaklaşık $1/2$ olasılıkla düşer ve böyle bir bölme problem boyutunu en az dörtte üç oranında küçültür. Sabit olasılıkla sabit oranda küçülme, logaritmik derinlik demektir. Yığıt derinliği de denetlenebilir: önce **küçük** parça özyinelemeye verilir, büyük parça döngüyle işlenirse yığıt derinliği en kötü durumda bile $O(\log n)$ kalır. ## Yinelenen Anahtarlar Dizinin tamamı aynı değerden oluşuyorsa, Lomuto bölümlemesi her elemanı küçük-eşit bölgesine koyar ve bölme yine dengesizleşir. Çözüm, diziyi **üç** bölgeye ayırmaktır: küçükler, eşitler, büyükler. ```python def uc_yollu_siralama(dizi: list[int]) -> list[int]: if len(dizi) <= 1: return list(dizi) pivot = dizi[len(dizi) // 2] kucuk = [x for x in dizi if x < pivot] esit = [x for x in dizi if x == pivot] buyuk = [x for x in dizi if x > pivot] return uc_yollu_siralama(kucuk) + esit + uc_yollu_siralama(buyuk) print(uc_yollu_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(uc_yollu_siralama([3, 3, 3, 3, 3])) # [3, 3, 3, 3, 3] ``` Eşitler bölgesi bir daha işlenmez; yalnızca birkaç farklı değer içeren dizilerde maliyet doğrusala yaklaşır. Buradaki yazım okunurluk için yeni listeler üretir; yerinde çalışan üç yollu bölümleme aynı fikri ek alan kullanmadan uygular. ## Seçme Problemi Bölümlemenin ikinci kullanımı, tüm diziyi sıralamadan **k'ıncı en küçük** elemanı bulmaktır. Bölümleme sonrası pivotun konumu bilindiğine göre, aranan eleman yalnızca bir tarafta olabilir; diğer taraf hiç işlenmez. ```python def hizli_sec(dizi: list[int], k: int) -> int: """k'ıncı en küçük eleman (k sıfırdan başlar).""" d = list(dizi) bas, son = 0, len(d) - 1 while True: if bas == son: return d[bas] p = bolumle(d, bas, son) if p == k: return d[p] if k < p: son = p - 1 else: bas = p + 1 veri = [5, 2, 9, 1, 5, 6] print(hizli_sec(veri, 0), hizli_sec(veri, 3), hizli_sec(veri, 5)) # 1 5 9 print(sorted(veri)[3]) # 5 ``` Beklenen maliyet $O(n)$'dir: her adımda problem boyutu sabit bir oranda küçülür ve maliyetler $n + n/2 + n/4 + \dots < 2n$ biçiminde toplanır. Sıralayıp k'ıncıyı okumak $O(n \log n)$ olurdu. Aynı problemin en kötü durumu da doğrusal olan bir çözümü vardır ("ortancaların ortancası"), ancak sabiti büyüktür ve pratikte rastgele pivotlu seçme tercih edilir. ## Özet - Hızlı sıralama pivota göre bölümler ve birleştirme adımı gerektirmez; yerinde çalışır, kararlı değildir. - Bölümleme $O(n)$ zaman ve $O(1)$ ek alan kullanır; pivot kesin yerine oturur. - Dengeli bölmede maliyet $\Theta(n \log n)$, dengesiz bölmede $\Theta(n^2)$'dir. - Belirli pivot seçimleri karesel girdilerle tetiklenebilir; rastgele pivot beklenen maliyeti girdiden bağımsız kılar. - Üç yollu bölümleme, yinelenen anahtarlarda maliyeti düşürür. - Aynı bölümleme, k'ıncı elemanı beklenen doğrusal maliyetle bulur. ## Sonraki Adım Hızlı sıralama yerinde çalışıyor ama en kötü durum güvencesi yok; birleştirmeli sıralamada güvence var ama ek alan gerekiyor. Sonraki ders ikisini birleştiren üçüncü yolu ele alacak: yığın sıralaması, Veri Yapıları kursundaki yığın yapısını kullanarak yerinde çalışır ve her durumda $O(n \log n)$ verir.