Hızlı Sıralama

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.

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ı

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.

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.

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.

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.