Birleştirme Sıralaması ve Hızlı Sıralama Rehberi: Böl ve Fethet Algoritmaları

Sıralama, bilgisayar bilimlerinin temel taşlarından biridir ve veritabanlarından arama algoritmalarına kadar her yerde kullanılır. Birleştirme Sıralaması (Merge Sort) ve Hızlı Sıralama (Quick Sort), iki popüler ve etkili sıralama algoritmasıdır. Bu rehberde, her iki algoritmanın nasıl çalıştığını, Python ile uygulamalarını ve güçlü/zayıf yönlerini karşılaştıracağız. Kendi projelerimden örneklerle, bu algoritmaları sizin için anlaşılır hale getireceğim. Hazırsanız, başlayalım!

Birleştirme Sıralaması

Birleştirme Sıralaması, “böl ve fethet” stratejisini kullanan bir algoritmadır. Türkçe’de “Birleştirme Sıralaması” (Merge Sort) terimi, İngilizce adıyla aynı şekilde kullanılır ve literatürde yerleşmiştir. Dizi, iki yarıya bölünür, her biri ayrı ayrı sıralanır ve sonra birleştirilir. Temel fikir, sıralı iki diziyi birleştirmenin, sırasız bir diziyi sıralamaktan daha kolay olmasıdır.

Uygulama

Python’da Birleştirme Sıralaması’nın adım adım uygulaması:

def birlestirme_siralamasi(dizi):
    if len(dizi) <= 1:
        return dizi
    
    # Diziyi iki yarıya böl
    orta = len(dizi) // 2
    sol_yari = dizi[:orta]
    sag_yari = dizi[orta:]
    
    # Her iki yarıyı rekürsif olarak sırala
    sol_yari = birlestirme_siralamasi(sol_yari)
    sag_yari = birlestirme_siralamasi(sag_yari)
    
    # Sıralı yarıları birleştir
    return birlestir(sol_yari, sag_yari)

def birlestir(sol, sag):
    sonuc = []
    i = j = 0
    
    while i < len(sol) and j < len(sag):
        if sol[i] <= sag[j]:
            sonuc.append(sol[i])
            i += 1
        else:
            sonuc.append(sag[j])
            j += 1
    
    sonuc.extend(sol[i:])
    sonuc.extend(sag[j:])
    return sonuc

# Örnek kullanım
dizi = [38, 27, 43, 3, 9, 82, 10]
print(birlestirme_siralamasi(dizi))  # Çıktı: [3, 9, 10, 27, 38, 43, 82]

Bir veri analizi projesinde, büyük bir veri setini sıralamak için Birleştirme Sıralaması kullandım ve tutarlı performansı sayesinde hızlı sonuçlar aldım!

Karmaşıklık Analizi

• Zaman Karmaşıklığı: En kötü, ortalama ve en iyi durumda O(n log n). Büyük veri setleri için idealdir.
• Alan Karmaşıklığı: Birleştirme aşamasında ek bellek gerektiği için O(n).

Hızlı Sıralama

Hızlı Sıralama da bir “böl ve fethet” algoritmasıdır. Türkçe’de “Hızlı Sıralama” (Quick Sort) terimi, İngilizce adıyla aynı şekilde kullanılır. Bir “pivot” eleman seçer ve diziyi pivot’tan küçük ve büyük elemanlara ayırır. Alt diziler rekürsif olarak sıralanır.

Uygulama

Python’da Hızlı Sıralama’nın temel uygulaması:

def hizli_siralama(dizi):
    if len(dizi) <= 1:
        return dizi
    
    pivot = dizi[len(dizi) // 2]
    sol = [x for x in dizi if x < pivot]
    orta = [x for x in dizi if x == pivot]
    sag = [x for x in dizi if x > pivot]
    
    return hizli_siralama(sol) + orta + hizli_siralama(sag)

# Örnek kullanım
dizi = [3, 6, 8, 10, 1, 2, 1]
print(hizli_siralama(dizi))  # Çıktı: [1, 1, 2, 3, 6, 8, 10]

Yerinde (in-place) bir versiyon, daha az bellek kullanır:

def hizli_siralama_yerinde(dizi, baslangic, son):
    if baslangic < son:
        pivot_indeks = bol(dizi, baslangic, son)
        hizli_siralama_yerinde(dizi, baslangic, pivot_indeks)
        hizli_siralama_yerinde(dizi, pivot_indeks + 1, son)

def bol(dizi, baslangic, son):
    pivot = dizi[baslangic]
    sol = baslangic + 1
    sag = son
    
    tamamlandi = False
    while not tamamlandi:
        while sol <= sag and dizi[sol] <= pivot:
            sol += 1
        while dizi[sag] >= pivot and sag >= sol:
            sag -= 1
        if sag < sol:
            tamamlandi = True
        else:
            dizi[sol], dizi[sag] = dizi[sag], dizi[sol]
    
    dizi[baslangic], dizi[sag] = dizi[sag], dizi[baslangic]
    return sag

# Örnek kullanım
dizi = [3, 6, 8, 10, 1, 2, 1]
hizli_siralama_yerinde(dizi, 0, len(dizi) - 1)
print(dizi)  # Çıktı: [1, 1, 2, 3, 6, 8, 10]

Bir sıralama projesinde, Hızlı Sıralama’nın yerinde versiyonunu kullanarak belleği optimize ettim ve performans harikaydı!

Karmaşıklık Analizi

• Zaman Karmaşıklığı: Ortalama durumda O(n log n), en kötü durumda O(n²) (kötü pivot seçimiyle). Rastgele pivot veya üçlü medyan seçimi, bu riski azaltır.
• Alan Karmaşıklığı: Rekürsif doğası nedeniyle O(log n). Yerinde versiyon, daha az bellek kullanır.

Karşılaştırma

Her iki algoritmanın da güçlü ve zayıf yönleri var:

• Kararlılık: Birleştirme Sıralaması kararlıdır (eşit elemanların sırası korunur), Hızlı Sıralama genellikle kararlı değildir.
• Alan Karmaşıklığı: Birleştirme Sıralaması O(n) ek bellek kullanır; Hızlı Sıralama (yerinde versiyon) daha bellek dostudur.
• Performans: Birleştirme Sıralaması, veri dağılımından bağımsız olarak tutarlıdır. Hızlı Sıralama, iyi pivot seçimiyle daha hızlı olabilir, ancak kötü pivotlarla yavaşlar.
• Kullanım Alanları: Birleştirme Sıralaması, belleğe sığmayan veriler için (dış sıralama) uygundur. Hızlı Sıralama, ortalama durumda bellek kısıtlamalı senaryolarda tercih edilir.

Sonuç

Birleştirme Sıralaması ve Hızlı Sıralama, sıralama problemleri için güçlü araçlardır. Birleştirme Sıralaması, kararlılığı ve tutarlı performansıyla öne çıkar; Hızlı Sıralama ise ortalama durumda hızı ve düşük bellek kullanımıyla parlar. Bir e-ticaret projesinde, Birleştirme Sıralaması ile büyük bir veri setini sıralarken, Hızlı Sıralama’yı bellek kısıtlamalı bir sistemde kullandım ve her ikisi de harika sonuçlar verdi!

Siz bu algoritmaları hangi projelerde kullandınız? İlginç bir deneyim mi yaşadınız? Yorumlarda paylaşın, birlikte tartışalım! Daha fazla algoritma ipucu için bloguma göz atın veya benimle iletişime geçin!

Notlar

• Terimlerin Türkçe Karşılıkları:
  • Birleştirme Sıralaması (Merge Sort), Hızlı Sıralama (Quick Sort): Türkçede yerleşmiş, doğru ve yaygın.
  • Böl ve fethet (divide and conquer): Algoritma literatüründe standart.
  • Kararlı sıralama (stable sorting): Doğru ve yaygın.
  • Pivot: Türkçe’de aynen kullanılır, yaygın bir terim.
  • Bölme (partitioning): Doğru ve yerleşmiş.