Merge Sort Algoritması Türkçesi ile Birleştirmeli Sıralama diyebileceğimiz bir tür sıralama algoritmasıdır. Bu yazıda merge sort algoritmasının mantığından, çalışma prensibinden bahsedip daha sonra merge sort algoritmasının akış diyagramını paylaşacağız. Ayrıca merge sort algoritmasının c koduna yazının en alt tarafındaki linkten ulaşabilirsiniz.
Merge Sort Algoritması (Birleştirme Sıralaması)
Merge Sort Algoritması, parçala ve fethet (divide and conquer) mantığı ile çalışan bir sıralama algoritmasıdır. Merge Sort Algoritması'nda temel olarak elimizdeki diziyi sürekli ortadan bölerek 2'şerli elemanlar haline gelene kadar parçalıyoruz. Daha sonra her bir 2'şerli elemanı kendi içerisinde sıralıyoruz ve diğer ikişerli elemanlar ile yine sıraları bozulmayacak şekilde birleştiriyoruz. Bu şekilde en sonunda sıralı diziyi elde etmekteyiz. Merge Sort Algoritması kısaca bu şekilde özetlenebilir. Şimdi Merge Sort Algoritması'na biraz daha detaylı olarak göz atalım.
Yukarıda aşağıda kaynağını belirttiğim wikimedia sitesinden alınmış Merge Sort Algoritması'nı çok güzel açıklayan bir GIF görmektesiniz. Burada başlangıçta karmaşık olarak duran 1-8 arası sayılar Merge Sort Algoritması ile sıralanmaktadır. Yukarıdaki örnek üzerinden algoritmamızın analizini yapmadan önce Merge Sort Algoritması'nın akış diyagramını sizlerle paylaşıyorum.
Merge Sort Algoritması (Birleştirme Sıralaması) Akış Diyagramı
Öncelikle Merge Sort Algoritması akış diyagramı üzerinden gidelim ve daha sonra yukarıda verdiğimiz örnek için akış diyagramımızı uygulayarak analizini yapalım.
Yukarıdaki resimdeki sağ taraftaki diyagram main fonksiyonumuzun diyagramıdır. Burada kullanıcıdan dizinin boyutunu ve elemanlarını almaktayız. Daha sonra ise diziyi "mergeSort" algoritmasına yolluyoruz. "mergeSort" fonksiyonundan sıralı olarak dönecek olan diziyi en sonda ekrana basıyoruz. "mergeSort" fonksiyonunun diyagramı sağ taraftakidir. Burada mergeSort fonksiyonuna gelen dizi parçasında bastaki elemanın indisi sondaki elemanın indisinden küçük olduğu sürece diziyi yarıya böleceğiz. Daha sonra ise her iki yarıyı tekrardan mergeSort fonksiyonuna yolluyoruz.
Yukarıdaki işlemler sonucunda elimizdeki diziyi 2 şerli olarak parçalamış ve her bir parçayı "Merge" fonksiyonuna göndermiş olduk. Merge kelime anlamı olarak birleştirme demek. Bu fonksiyonda da yapacağımız iş birleştirme olacak. Merge fonksiyonunda 2 li olarak gelen dizi parçalarını kendi içerisinde sıralayacağız. Daha sonra ikilileri kendi aralarında, daha sonra dörtlüleri kendi aralarında sıralayarak dizinin boyutuna göre ilerliyoruz. Bu şekilde sıralı diziyi Merge Sort Algoritması ile elde etmiş olduk. Şimdi merge sort algoritmasını kısaca bir özetleyelim.
Merge Sort Algoritması Özet
- Diziyi ortadan ikiye böl ve daha sonra her bir grup 2 elemanlı kalana kadar her bir grubu kendi içerisinde ikiye böl.
- Elde edilen ikişerli grupları kendi aralarında sırala.
- Kendi içlerinde sıralı olan ikili grupları komşu gruplarla birleştirerek sırala.
- Bir önceki işlemi dizinin boyutu elverdiği sürece devam ettir ve sıralı diziyi elde et.
Kaynak
