Merge Sort Nasıl Çalışır? Birleştirme Sıralaması Adım Adım Örnek

Merge sort nasıl çalışır sorusunun cevabı, diziyi küçük parçalara ayırıp bu parçaları sıralı biçimde yeniden birleştirmeye dayanır. Birleştirme sıralaması olarak da adlandırılan bu algoritmada dizi, tek elemanlı parçalara kadar bölünür; ardından küçük sıralı listeler karşılaştırılarak daha büyük sıralı listeler oluşturulur.

Bu yaklaşım, böl ve yönet yöntemini kullanır. Büyük bir problemi daha küçük alt problemlere ayırır, her alt problemi çözer ve elde edilen sonuçları bir araya getirir.

Merge sort ve böl ve yönet nasıl çalışır?

Merge sort, diziyi ortadan iki parçaya ayırır ve her parçayı aynı yöntemle daha küçük parçalara bölmeye devam eder. Parçalar tek elemana ulaştığında her biri kendi içinde sıralı kabul edilir, çünkü tek elemanlı bir listenin sırasını değiştirmeye gerek yoktur.

Özyineleme, bir fonksiyonun kendisini daha küçük bir girdiyle yeniden çağırmasıdır. Merge sort içinde fonksiyon, dizinin sol ve sağ parçaları için tekrar çalışır. Liste boşsa veya tek eleman içeriyorsa işlem durur. Bu iki durum, özyinelemenin durma koşulunu oluşturur.

Sonraki aşamada sıralı parçalar birleştirilir. Birleştirme sırasında iki listenin başındaki elemanlar karşılaştırılır ve küçük olan yeni listeye eklenir. Seçilen eleman kendi listesinden çıkarılmış gibi düşünülür ve karşılaştırma, o listenin yeni başındaki elemanla sürer.

Bölme işlemi problemi küçültürken birleştirme işlemi çözümleri yeniden düzenler. Bu ilişkiyi farklı örnekler üzerinden düşünmek için algoritmik düşünme testini deneyebilirsin. NIST algoritma sözlüğünde de merge sort, iki grubu özyinelemeli olarak sıralayıp sonrasında birleştiren bir algoritma olarak açıklanır.

Dizi adım adım nasıl bölünür ve birleştirilir?

Örnek dizimiz [38, 27, 43, 3, 9, 82, 10] olsun. İlk aşamada dizi ortadan iki parçaya ayrılır. Her parça tek elemanlı listelere kadar bölündükten sonra birleştirme işlemi başlar.

Örneğin [27, 38, 43] ile [3, 9, 10, 82] birleştirilirken önce 27 ile 3 karşılaştırılır ve 3 seçilir. Ardından 27 ile 9 karşılaştırılır, bu kez 9 seçilir. Aynı işlem, bir listenin elemanları bitene kadar sürer.

Bir listenin elemanları tükendiğinde diğer listedeki kalan elemanlar doğrudan sonuca eklenir. Böylece karşılaştırmalar tamamlanır ve başlangıçtaki dizi, [3, 9, 10, 27, 38, 43, 82] biçiminde sıralanmış olur.

Python ile merge sort nasıl yazılır?

Merge sort'u Python'da yazarken listeyi önce boş ya da tek elemanlı parçalara kadar bölersin, ardından sıralanmış parçaları yeniden birleştirirsin. Aşağıdaki fonksiyonda i ve j indisleri, sıralı sol ve sag listelerinde hangi elemanın karşılaştırılacağını takip eder.

def merge_sort(dizi):
    if len(dizi) <= 1:
        return dizi

    orta = len(dizi) // 2

    sol = merge_sort(dizi[:orta])
    sag = merge_sort(dizi[orta:])

    sonuc = []
    i = 0
    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


dizi = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(dizi))

Programın çıktısı [3, 9, 10, 27, 38, 43, 82] olur. len(dizi) <= 1 koşulu, boş listede veya tek elemanlı listede durmayı sağlar. Böyle bir liste zaten sıralı kabul edildiği için doğrudan geri döndürülür; aynı kural yinelenen değerler içeren listelerde de çalışmaya devam eder.

orta = len(dizi) // 2 ifadesindeki //, sonucu tam sayı olarak verir. dizi[:orta] diliminde orta indis alınmaz, dizi[orta:] diliminde ise orta indis sağ parçanın ilk elemanı olur. Python dilimlerinin yeni listeler oluşturması nedeniyle bu yaklaşım, parçaları birbirinden ayrı listeler olarak işler.

Birleştirme sırasında iki parçanın ilk bekleyen elemanı karşılaştırılır ve küçük olan sonuc listesine eklenir. Parçalardan biri tamamen kullanıldığında diğer parçada kalan elemanlar extend() ile doğrudan sonuca eklenir. Python sözdizimini ve liste işlemlerini uygulamalı olarak pekiştirmek için ücretsiz Sıfırdan Temel Python video eğitimi de kullanılabilir.

Merge sort ne kadar zaman ve bellek kullanır?

Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresi veya kullandığı kaynakların nasıl arttığını anlatır. Merge sort'ta liste her adımda yaklaşık ikiye bölündüğü için bölme seviyeleri logaritmik sayıda oluşur.

Her seviyede bütün elemanlar sıralı parçaları birleştirmek için yaklaşık bir kez kontrol edilir. Bu seviyelerin her birindeki toplam iş O(n), seviye sayısı ise O(log n) olduğu için toplam zaman karmaşıklığı O(n log n) olur. MIT OpenCourseWare kaynaklarında da merge sort için aynı bölme ve doğrusal birleştirme ilişkisi kullanılır.

Bu Python uygulamasında dilimler ve birleştirme sırasında oluşturulan sonuç listeleri nedeniyle tepe ek bellek kullanımı O(n) düzeyindedir. Özyinelemeli çağrılar ayrıca yaklaşık O(log n) büyüklüğünde bir çağrı yığını oluşturur; bu iki değer, uygulamanın aynı anda kullandığı belleği anlatır. İşlem boyunca oluşturulan tüm geçici listelerin toplam tahsisi ise tepe kullanımından farklı bir ölçüdür.

Karşılaştırma için Bubble Sort, elemanları komşu karşılaştırmalarla düzenleyen ve genellikle O(n²) zaman karmaşıklığıyla anılan bir yöntemdir. Merge sort'un avantajı, büyüyen girdilerde çalışma maliyetinin n ile logaritmik bir çarpanın birlikte artmasıdır.

Uygulamada hangi hatalara dikkat etmelisin?

Merge sort uygulamasını kontrol ederken bölme sınırlarına, durma koşuluna ve birleştirme sonunda kalan elemanlara dikkat etmelisin. Küçük listelerle yapacağın denemeler, bu noktalardaki hataları fark etmene yardımcı olur.

• Birleştirme sonunda kalan elemanları ekle: İki sıralı parçadan biri önce tükendiğinde diğerinde eleman kalabilir. Kalanları sonuca eklemezsen sıralanmış listede bazı değerler eksik olur. Bunu, iki parçanın farklı uzunlukta olduğu bir örnekte giriş ve sonuç listelerindeki eleman sayısını karşılaştırarak fark edebilirsin.
• Boş listeyi de kapsayan bir durma koşulu kullan: Uzunluğu sıfır veya bir olan listeler daha fazla bölünmeden döndürülmelidir. Yalnızca tek elemanlı listeyi durma koşulu olarak seçersen boş liste bölünmeye devam eder ve özyineleme hatasına yol açabilir. Fonksiyonu boş listeyle de dene.
• Orta noktayı iki dilimde tutarlı kullan: Python'da sol parça için liste[:orta], sağ parça için liste[orta:] kullanabilirsin. Sınırlar arasında boşluk bırakırsan bir eleman kaybolabilir, sınırları örtüştürürsen bir eleman iki kez işlenebilir. Özellikle tek sayıda eleman içeren bir listeyle deneme yaparak sonucu kontrol et.

Sık Sorulan Sorular

Merge sort aynı değeri taşıyan elemanların sırasını korur mu?

Merge sort, birleştirme sırasında eşit değerler arasından önce sol parçadaki eleman seçilirse bu elemanların başlangıçtaki göreli sırasını korur. Bu özelliğe kararlı sıralama denir ve uygulamadaki eşitlik tercihine bağlıdır.

Merge sort boş bir listeye uygulandığında ne döndürür?

Durma koşulu boş listeyi kapsayan bir merge sort uygulaması, boş listeye uygulandığında boş bir liste döndürür. Böylece listeyi daha fazla bölmeye çalışmadan işlem tamamlanır.

Bu kontrollerle kendi uygulamanı farklı uzunluktaki listelerde deneyebilir ve sonuçları karşılaştırabilirsin.