Merhabalar,
Bugün sıralama algoritmaları yazı dizimizin dördüncü bölümü olan birleştirmeli sıralama (Merge sort) ile karşınızdayım. Merge sort nedir, algoritması nedir, merge sort kodları gibi konularda yazacağım.
Diğer algoritmalarda yaptığımız gibi bu yazımızın başında da sıralama algoritması nedir, sıralama nedir isimli girişimizi yapalım.
Sıralama ve arama tekniklerinden pek çok programda yararlanılmaktadır. Günlük yaşamımızda elemanların sıralı tutulduğu listeler yaygın olarak kullanılmaktadır. Sıralama, sıralanacak elemanlar bellekte ise içsel kayıtların bazıları ikincil bellek ortamında ise dışsal sıralama olarak adlandırılır.
Açıklamayı da yaptıktan sonra konumuza geçebiliriz.
Merge Sort
Verinin hafızada sıralı tutulması için geliştirilmiştir. Basitçe inceleyecek olursak diziyi ikişer elemanlı kalana kadar parçalara iner sürekli olarak ikiye böler. Sonra bu parçaları kendi içlerinde önce sıralar ve daha sonra birleştirme işlemini gerçekleştirir. Sonuçta elde edilen dizi sıralı dizinin kendisi olur. Bu açıdan incelendiğinde parçala fether (divide and conquere) yapısıdır. Sıralı iki veri grubunu birleştirerek üçüncü bir sıralı veri grubu elde etmeye dayanır.
Merge Sort Kodu (Java)
public class MergeSort { private int[] list; public void sort() { list = sort(list); } private int[] sort(int[] whole) { if(whole.length==1) { return whole; } else { int[] left=new int[whole.length/2]; System.arraycopy(whole,0,left,0,left.length); int[] right=new int[whole.length-left.length]; System.arraycopy(whole,left.length,right,0,right.length); left=sort(left); right=sort(right); merge(left,right,whole); return whole; } } private void merge(int[] left, int[] right, int[] result) { int x=0;int y=0;int k=0; while( x<left.length&&y<right.lenth) { if(left[x]<right[y]) { result[k]=left[x]; x++; } else { result[k]=right[y]; y++; } k++; } int[] rest, restIndex; if(x>=left.length) { rest=right; restIndex=y; } else { rest=left; restIndex=x; } for(int i=restIndex; i<rest.length;i++) { result[k]=rest[i]; k++; } }
Merge sortun kodu da bu şekilde oluşur.
Merge Sort Performansı
Merge sort’un çalışma zamanını inceleyecek olursak:
•logaritma 2 tabanında n defa olmak üzere ve her turda n veya daha az kez karşılaştırma olacağından O(n*logaritma 2 tabanında n) kez karşılaştırma olur.
•Quicksort için en kötü durumda O(n²) karşılaştırma gerektiği düşünülürse daha avantajlı bir durum oluşur fakat merge sort’ta atama işlemleri fazla ve dizi için fazla yer gerektirir.
Bu yazımızda da sizlere merge sort ile ilgili bilgi vermeye çalıştım. Anlamadığınız veya eksik gördüğünüz kısımları bana yorumlar aracılığı ile iletebilirsiniz.
Teşekkürler!