Sorting/Sıralama algoritmaları daha önceden de söylediğim gibi bir kod dilini öğrenirken fazlasıyla önemli. Yani dili gerçekten anlamak istiyorsanız, üzerinde bir kaç farklı sorting algoritması uygulamanız yararınıza olacaktır. Bu sebeple hem dilleri hem algoritmaları göstermek adına çeşitlendirme yapmak istediğim için Merge Sort algoritmasının da Python ile uygulanmasını gösterebilirim diye düşündüm.
Merge Sort algoritmasını sözlü olarak anlatmaya çalışırsam; bir listeyi ikili sayılar halinde kalacak şekilde parçalıyor, sonra her ikili de hangisi (sağ/sol) daha büyük diye bakıyor, ve küçük olanı sola koyuyoruz. Ardından her ikili başka bir ikiliyi ile karşılaştırıyoruz, birincinin ilk öğesi ikincinin ilk öğesinden küçük mü, küçüğü sola alıyoruz, ardından yine aynı öğe ikincinin ikincisinden de küçük mü, küçüğü sola alıyoruz ve böylece de dörtlüler oluşuyor. Ardından her dörtlüyü başka bir dörtlüyle karşılaştırıyoruz, yine aynı şekilde her elemanı tek tek, küçük olanlar sola alıyoruz ve böyle böyle liste tamamlanıyor. Eğer başka algoritmalar üzerinde biraz uğraşıysanız bu pek de hızlı bir algoritma değil gibi hissedebilirsiniz; evet, yine Divide & Conquer (Böl ve Yönet) kafası bir algoritma ama fazla karşılaştırma var diyebilirsiniz. Ancak Merge Sort un da yararlı olduğu durumlar söz konusu, tahminimce en iyi oldukları durum için değil ama en kötü oldukları durumlar için Merge Sortun, Quick Sortu bile geçtiği oluyordur. Quick Sort içinde pivot seçimi kritik bir seçim olduğundan ve Merge Sort ona göre daha stabil, istikrarlı olduğundan bunu seven pek çoklarını da gördüm.
Bu uygulamayı, çok yerde görebileceğiniz üzere 2 parçadan oluşacak şekilde yapmak daha iyi ve temiz gözüktüğü için ben de öyle gidiyorum. İlk fonksiyon birlestirme fonksiyonu bu asıl Merge işini yapan işlemleri barındırıyor. Tabii ki hangisinin küçük olduğuna burda bakılıp o sola atılıyor, sonra parçadaki her sayı için bu kontrol yapılıyor:
def birlestir(sol, sag):
siraliliste = []
i = k = 0
while i < len(sol) and k < len(sag):
if sol[i] < sag[k]:
siraliliste.append(sol[i])
i += 1
else:
siraliliste.append(sag[k])
k += 1
siraliliste += sol[i:]
siraliliste += sag[k:]
return siraliliste
def mergeSort(sirasizliste):
if len(sirasizliste) < 2:
return sirasizliste
b = int(len(sirasizliste) / 2)
return birlestir(mergeSort(sirasizliste[:b]), mergeSort(sirasizliste[b:]))
print(mergeSort([4,1,9,6,3,2,10,7,5,8]))
İkinci fonksiyon ise ana çalıştırılan fonksiyon, ilk fonksiyon da burada çağırılıyor. Burada listeyi ikiye bölüp, her parçaya tekrar bu fonksiyonun kendisini uygularak birleştirmek üzere birleştiri çağırıyoruz. Ancak bu recursive (kendini çağıran) işlem sırasında dikkat etmeniz gereken, o parçaların da kendi yarıları için aynı fonksiyonu çağırdığı ve sonuçları birleştirilmek üzere bir üste ilettikleri. Böylece yarılar en küçük parçalara kadar küçülüp kendilerini sıralayıp, ayrıldıkları yarıları ile birleşerek işlemi tekrarlamış oluyorlar. Başka bir detay ise ikiye böldüğüm len yani uzunluk fonksiyonunu integer a dönüşütürmem, eğer bunu yapmazsanız en azından Python3 te "slice indices must be integers or None or have an __index__ method" şeklinde float hatası almanız olasıdır.