Python Merge Sort Eğitimi

Veri sıralama, veri uzmanlarının günlük çalışmalarında en sık yaptıkları işlemlerden biridir. Çoğu zaman anlamlı içgörüler çıkarabilmek için verileri belirli bir düzende göstermemiz gerekir. Neyse ki günümüzde bu işi elle yapmak zorunda değiliz. Bilgisayarlar bu sihri bizim için rakipsiz bir performansla gerçekleştirebiliyor.

Veri sıralamak için birden fazla strateji vardır. Bu eğitimde, en etkili sıralama tekniklerinden birini inceleyeceğiz. “Merge sort” (birleştirmeli sıralama) algoritması, sıralanmamış bir diziyi önce daha küçük dizilere ayıran, ardından bunları doğru sırayla birleştiren böl-ve-fethet yaklaşımını kullanır. 

İlerleyen bölümlerde, merge sort algoritmasının tüm ayrıntılarını, Python'daki görünümünü ve sorunsuz bir uygulama için bazı pratik ipuçlarını ele alacağız.

Merge Sort Nedir?

Pek çok sıralama algoritması vardır, ancak merge sort'tan daha iyi performans gösteren birini bulmak zordur. Şaşırtıcı olmayan bir şekilde, bu algoritma büyük veritabanlarını sıralamak veya sıradan bir bilgisayardaki dosyaları düzenlemek gibi her türlü gerçek dünya uygulamasında kullanılır.

Algoritma, üç bölüme ayrılabilen böl-ve-fethet paradigmasına dayanır:

• Böl: sorun daha küçük alt sorunlara ayrılır. 
• Fethet: alt sorunlar özyinelemeli (rekürsif) olarak çözülür. 
• Birleştir: alt sorunların çözümleri bir araya getirilerek nihai çözüme ulaşılır.

Böl ve fethet stratejisi

Merge sort nasıl çalışır, bakalım. Diyelim ki aşağıdaki sayıları merge sort algoritmasını uygulayarak sıralamak istiyoruz. Algoritma, verileri özyinelemeli olarak iki parçaya böler ve her listenin tek bir öğesi kalana kadar bölmeye devam eder. Ardından, bunları başka bir listede sıralayarak birleştiririz.

Merge Sort Problemi. Kaynak: DataCamp

Merge Sort'un Zaman ve Alan Karmaşıklığı

Belirli bir problem için en iyi çalışan sıralama algoritmasını önceden bilmek imkânsızdır. Algoritmanın kendisinin ötesinde, kodun yazıldığı programlama dili, çalıştırıldığı donanım ve sıralanacak verilerin özellikleri gibi pek çok değişken dikkate alınmalıdır. 

Bir sıralama algoritmasının tam çalışma süresini öngöremesek de, zaman ve alan karmaşıklığını analiz ederek çeşitli sıralama algoritmalarının performansını karşılaştırabiliriz.

Merge sort'un zaman karmaşıklığı

Büyük O Gösterimi ve Zaman Karmaşıklığı üzerine ayrı bir rehberde açıkladığımız gibi, zaman karmaşıklığı analizinin amacı bir algoritmanın tam çalışma süresini tahmin etmek değil, giriş verisi miktarı arttıkça çalışma süresinin nasıl değiştiğini inceleyerek algoritmanın ne kadar verimli olduğunu değerlendirmektir.

Zaman karmaşıklığı analizi, bir fonksiyonun hangi hızda büyüdüğünü veya azaldığını tanımlayan matematiksel bir gösterim olan Büyük O ile yazılır. Merge sort, O(N log(N)) olarak gösterilen log-lineer ya da lineeritimik zaman karmaşıklığına sahiptir; burada N listedeki öğe sayısını ifade eder. 'O' harfi, büyümenin 'mertebesi'ni temsil eder. 

Zaman karmaşıklığı analizinde lineeritimik karmaşıklık kabaca lineer karmaşıklığa benzer davranır; yani yürütme süresi doğrudan veri miktarıyla orantılıdır. Dolayısıyla veri miktarı iki katına çıkarsa, algoritmanın veriyi işlemesi için gereken süre de iki katına çıkmalıdır; başka bir deyişle bölme ve birleştirme sayısı iki katına çıkar.

Merge sort'un zaman karmaşıklığı lineer davrandığından, en iyi, ortalama ve en kötü durumlarda karmaşıklığı aynıdır. Bu da, giriş sıralaması ne olursa olsun, algoritmanın işi tamamlamak için her zaman aynı sayıda adım atacağı anlamına gelir.

Merge sort'un alan karmaşıklığı

Son olarak, görevi tamamlamak için gereken zamanın yanı sıra, algoritma karmaşıklığını analiz ederken bir diğer önemli husus, problem büyüdükçe algoritmanın tamamlanması için ne kadar belleğe ihtiyaç duyacağını tahmin etmektir. 

Bunu alan karmaşıklığı ve yardımcı (ek) alan kavramları kapsar. Yardımcı alan, bir algoritma tarafından kullanılan ekstra ya da geçici alanı ifade ederken; alan karmaşıklığı, giriş boyutuna göre algoritmanın kapladığı toplam alanı ifade eder. Başka bir deyişle, alan karmaşıklığı hem yardımcı alanı hem de girdinin kullandığı alanı içerir.

Merge sort'un alan karmaşıklığı O(N)'dir. Bunun nedeni, giriş dizisinin sıralanmış yarılarını birleştirmek için N boyutunda bir yardımcı dizi kullanmasıdır. Yardımcı dizi, birleştirilmiş sonucu saklamak için kullanılır ve giriş dizisi sıralanmış sonuçla üzerine yazılır.

Python'da Merge Sort Uygulaması

Haydi merge sort algoritmasını Python'da uygulayalım. Algoritmayı kodlamanın birkaç yolu vardır; ancak, anlaşılması görece en kolay olan ve yinelemeye dayalı diğer alternatiflere göre daha az satır kod gerektiren, özyinelemeye (rekürsiyona) dayalı sürüme sadık kalacağız.

Merge sort'ta özyinelemeyi anlamak

Konuya yeniyseniz, programlamada özyineleme, bir fonksiyonun kendisini çağırmasıdır. Bu güçlü fonksiyonlar hakkında her şeyi öğrenmek için Python'da Özyinelemeli Fonksiyonları Anlamak başlıklı eğitimimize göz atabilirsiniz.

Merge sort'u uygulamak için önce temel durumu tanımlarız: liste yalnızca bir öğe içeriyorsa zaten sıralıdır, dolayısıyla hemen döneriz. Aksi halde, listeyi iki yarıya, left_half ve right_half olarak böler ve her biri üzerinde merge_sort()'u özyinelemeli olarak çağırırız. Bu süreç, tüm alt listeler tek bir öğe içerecek hale gelene kadar devam eder.

Bu sıralı alt listelere sahip olduğumuzda birleştirme işlemine başlarız. Bunu yapmak için üç indeks değişkeni başlatırız: left_half içindeki konumu izlemek için i, right_half için j ve nihai birleştirilmiş liste için k. Daha sonra her iki yarıdan öğeleri karşılaştırırız. Eğer left_half'taki mevcut öğe daha küçükse, onu my_list[k] içine yerleştirir ve i'yi ilerletiriz. Aksi halde right_half'taki öğeyi alır, my_list[k]'ye koyar ve j'yi artırırız. Her karşılaştırmadan sonra, nihai listedeki bir sonraki konuma geçmek için k'yı ilerletiriz.

Bu süreç, yarılardan birindeki tüm öğeleri karşılaştırana kadar devam eder. left_half veya right_half'ta kalan öğeler varsa, hiçbir verinin geride kalmamasını sağlamak için bunları doğrudan nihai listeye ekleriz. Merge sort özyinelemeli çalıştığından, bu birleştirme işlemi tüm özyineleme seviyelerinde yürütülür ve tüm liste sıralanıncaya kadar devam eder.

Python uygulaması

Aşağıda, örnek olarak önceki diyagramdaki sıralanmamış listeyi kullanan kodu bulabilirsiniz:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]Altyapı:

Merge Sort ve Diğer Sıralama Algoritmaları

Merge sort oldukça hızlı bir sıralama algoritmasıdır; özellikle büyük veritabanları için uygundur ve sıklıkla diğer algoritmalar için bir kıyas olarak kullanılır. Ancak, daha kısa listelerde performansı diğer sıralama algoritmalarına kıyasla daha düşük olma eğilimindedir.

Aşağıdaki tabloda, merge sort'un diğer popüler sıralama algoritmalarıyla karşılaştırmasını bulabilirsiniz.

Merge Sort'un Pratik Uygulamaları

Merge sort, büyük listeleri sıralarken yüksek performans gösterir; ancak daha küçük listelerde verimliliği düşer. Benzer şekilde, giriş listelerinde belirli bir ölçüde düzen zaten varsa daha az etkilidir; çünkü merge sort, listenin sırası ne olursa olsun aynı adımları uygular.

Merge sort'un özellikle kullanışlı olduğu harika bir kullanım alanı bağlı listelerdir. Bağlı liste, düğümlerin birbirine doğrusal olarak bağlanmasından oluşan bir veri yapısıdır. Her düğüm, veriyi ve bir sonraki düğüme bağını içerir.

Merge sort, yalnızca verilere sıralı erişim gerektirdiğinden bağlı listeler için tercih edilir; bu da bağlı listelerin doğasıyla iyi örtüşür. Ayrıca merge sort stabil bir sıralama algoritmasıdır (yani eşit öğelerin göreli sırasını korur); bu, bağlı listelerin düzenini korumada çok önemli bir husustur.

Yaygın Hatalar ve Sorun Giderme

Merge sort algoritması oldukça yalındır ve kodda iyileştirme alanı sınırlıdır. Ancak, giriş verisinin boyutunu dikkate alarak sıralama stratejinizin karmaşıklığını artırabilirsiniz. 

Merge sort'un daha büyük veri setlerinde daha iyi çalıştığını zaten belirtmiştik. Daha küçük veri setleri için, ekleme sıralaması (insertion sort) gibi O(N^2) zaman karmaşıklığına sahip diğer sıralama algoritmaları daha iyi çalışabilir. Bu durumda, belirli bir boyut eşiği tanımlayıp bunun altındaki durumlarda merge sort yerine insertion sort'a geçmeniz yeterli olurdu.

Bunun dışında, keşfedilebilecek iyi bir fikir paralelleştirmedir. Merge sort'un adımları yeterli işlem gücüyle kolayca paralelleştirilebilir ve böylece tamamlama süresi azaltılabilir. Paralel hesaplama hakkında daha fazla bilgi edinmek için CPU ve GPU rehberimizi okuyun. 

Sonuç

Merge sort, mevcut en etkili ve popüler sıralama algoritmalarından biridir; ancak algoritmaların harika ve sürekli genişleyen evreninde öğrenilecek çok daha fazlası var. Algoritmaların teknik ayrıntılarına, nasıl çalıştıklarına, ilişkili karmaşıklıklarına, güçlü ve zayıf yönlerine ilgi duyuyorsanız, öğreniminizi sürdürmenize yardımcı olabilecek şu DataCamp kaynaklarına göz atın:

• Veri Yapılarına ve Algoritmalara Giriş Kursu 
• Python Programlama Beceri Rotası
• Python Veri Temelleri Beceri Rotası
• Orta Düzey Python Kursu
• Python ile Veri Analisti Kariyer Rotası 
• Büyük O Gösterimi ve Zaman Karmaşıklığı