Yan yana

Merge SortvsQuicksort

Birleştirmeli sıralama (merge sort) ile hızlı sıralama (quicksort) arasındaki fark nedir?

Güncellendi 30 Eylül 20262 dk okuma6 fark

Kısaca

Merge sort O(n log n) zamanı garanti eder ama ek bellek ister; quicksort ise pivot etrafında yerinde bölümler, genelde daha hızlıdır ama O(n²)'ye düşebilir.

Veri Yapılarıs. 26

Merge Sort

Merge sort, bir listeyi ikiye bölen, her yarıyı özyinelemeyle sıralayan ve sıralı yarıları O(n log n) sürede birleştiren böl ve yönet sıralama algoritmasıdır.

Merge Sort sayfasını oku

Veri Yapılarıs. 28

Quicksort

Quicksort, öğeleri seçilen bir pivot etrafında bölümleyen, sonra küçük ve büyük grupları aynı şekilde sıralayan bir böl ve yönet sıralama algoritmasıdır.

Quicksort sayfasını oku

Merge Sort ve Quicksort karşılaştırması

Özellik	Merge Sort	Quicksort
Strateji	İkiye böl, her yarıyı sırala, sonra birleştir	Pivot etrafında bölümle, sonra her tarafı sırala
Ortalama süre	O(n log n)	O(n log n), pratikte genellikle daha hızlı
En kötü durum süresi	O(n log n), garantili	Sürekli kötü pivotlarla O(n²)
Ek bellek	Dizileri birleştirmek için O(n)	Özyineleme için O(log n); yerinde sıralar
Kararlılık	Kararlı: eşit elemanlar sırasını korur	Tipik gerçeklemelerde kararlı değil
İyi çalıştığı yer	Bağlı listeler ve belleğe sığmayan veriler	Bellekteki diziler; iyi önbellek kullanımı sayesinde

Fark, açıklamalı

Merge sort ve quicksort, ikisi de böl ve yönet (divide-and-conquer) türünde sıralama algoritmalarıdır: problemi daha küçük parçalara böler, onları çözer ve sonuçları birleştirirler. Merge sort listeyi iki yarıya böler, her birini özyinelemeli olarak sıralar ve sıralanmış iki yarıyı birleştirir. Quicksort bir pivot eleman seçer, listeyi küçük elemanlar sola, büyükler sağa gidecek biçimde bölümler ve sonra her tarafı sıralar.

Zor işi farklı yerlere koyarlar. Merge sort'un bölme adımı basittir, işi birleştirme adımı yapar; bu her zaman O(n log n) zaman alır ama dizilerde O(n) ek bellek gerektirir. Quicksort'un bölümleme adımı işi yerinde yapar, az ek bellek kullanır ve ortalamada çok hızlı çalışır; ama pivotlar sürekli kötüyse, örneğin hep en küçük eleman seçiliyorsa, O(n²)'ye yavaşlar.

Gerçek dünyadaki sıralama fonksiyonları çoğu zaman bunları başka algoritmalarla birleştirir. Introsort quicksort ile başlar ve özyineleme fazla derinleşirse heapsort'a geçer; Python'da ve Java'da nesneler için kullanılan Timsort tarzı algoritmalar ise merge sort ile ekleme sıralamasına dayanır.

Sık yapılan bir yanlış, quicksort'un her zaman en iyi seçim olduğu düşüncesidir. Bellekteki diziler için ortalamada hızlıdır; ama merge sort kararlıdır (eşit elemanlar özgün sıralarını korur), en kötü durumu garantilidir ve bağlı listelere ve belleğe sığmayacak kadar büyük verilere uygundur.

Hangisini kullanmalısınız?

Merge Sort şu durumlarda doğru seçim:

Eşit elemanları sırasında tutan kararlı bir sıralamaya ihtiyacınız var.
Garantili en kötü durum, ortalama hızdan daha önemli.
Bir bağlı listeyi ya da diskte duran veriyi sıralıyorsunuz.

Quicksort şu durumlarda doğru seçim:

Bellekteki dizileri sıralıyor ve en iyi ortalama hızı istiyorsunuz.
Ek bellek sınırlı.
Verileriniz için kararlılık önemli değil.

İki algoritma da Python'da

Merge Sortpython

def merge_sort(xs):
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):  # merge step
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Quicksortpython

# Simple version for clarity; production quicksort
# partitions the array in place instead of copying
def quicksort(xs):
    if len(xs) <= 1:
        return xs
    pivot = xs[len(xs) // 2]
    smaller = [x for x in xs if x < pivot]
    equal = [x for x in xs if x == pivot]
    larger = [x for x in xs if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)

Sık sorulan sorular

Merge sort mu quicksort mu daha hızlı?

Quicksort, yerinde çalıştığı ve CPU önbelleğini iyi kullandığı için bellekteki dizilerde genellikle daha hızlıdır. Garantili O(n log n) en kötü duruma ihtiyacınız olduğunda ya da bağlı listeleri veya çok büyük verileri sıraladığınızda merge sort kazanır.

Quicksort kararlı mı?

Olağan yerinde biçiminde değil, bu yüzden eşit elemanların sırası değişebilir. Merge sort kararlıdır; kayıtları önce bir alana, sonra başka bir alana göre sıraladığınızda bu önemlidir.

Quicksort'un neden O(n²) en kötü durumu var?

Pivot hep en küçük ya da en büyük eleman olursa, her bölümleme yalnızca bir eleman eler ve özyineleme n seviye derine iner. Rastgele ya da üçün ortancası (median-of-three) pivotlar seçmek bunu çok olasılık dışı kılar.