4. Birleştirmeli Sıralama (Merge Sort)

Merge sort’un özelliği problemi parçalara bölmesidir ve problem parçalara bölündüğünde zaman karmaşıklığı logaritmik zamana iner. Bu da exponiensel olanlara göre çok daha iyi sonuç vermesi anlamına gelmektedir. 

Merge sort’ta ana mantık parçala ve fethet’dir. Parçala ve fethet’in mantığı ;
1. Problem küçük parçalara bölünür.
2. Daha küçük parçalara bölünen problemler çözülür.
3. Çözülmüş küçük parçalar tekrar birleştirilir.

yukarıdaki örnek üzerinden merge sort konseptini açıklamaya çalışıcam.

  • Öncelikle elimizde 1,6,9,15,18,26,32,43 elemanlarını barındıran bir dizi olduğunu varsayalım. Merge sort divide and conquer mantığına dayanarak bu diziyi en ufak parçaya ulaşıncaya kadar böler. Yani 8 elemanlık dizi 4-4 daha sonra 2-2-2-2 ve son olarak da 1-1-1-1-1-1-1-1 şeklinde en ufak parçaya bölünür.
  • Böldüğü en ufak parçaları tekrar eski haline birleştirir ancak bu sefer sıralayarak birleştirir. Örneğin elimizde 9 ve 1 var bunları tekrar birleştirirken 1 9 diye sıralayarak birleştirir. Ve ilk birleştirmede elimizde  kendi içinde sıralı 2şer elemanlı 4 grup olmuş olur. 2. Birleştirmede kendi içinde sıralı 4er elemanlı 2 grup ve son birleştirmede de sıralı 8 elemanlı diziyi elde etmiş oluruz.
  • Sıralama işleminin yapılışı şu şekilde ; örneğin 18 26 – 6 32 elemanlarında 4 elemanlı sıralı bir grup elde etmek istiyoruz. Her birinin karşılıklı indislerini kıyaslarız.  18 mi küçük 6 mı .. 6  en başa koy..18mi 32 mi 18 … 26 mi 32 mi 26 ve en son da 32..
    4lü grupların birleşmesinden oluşan sıralı 8li de şu şekilde oluşur.  6-1 = 6 ..6-9=6…9-18=9…26-43=26…32-43=32….43

ALGORITMA ANALIZI

 

MERGE SORT C# IMPLEMENTASYONU

 static void merge(List<double> arr, int l, int m, int r)
 {
    int n1 = m - l + 1;
    int n2 = r - m;

   double[] L = new double[n1];
   double[] R = new double[n2];

   for (int t = 0; t < n1; ++t)
    L[t] = arr[l + t];
   for (int z = 0; z < n2; ++z)
    R[z] = arr[m + 1 + z];

    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2)
    {
      if (L[i] <= R[j])
     {
      arr[k] = L[i];
       i++;
     }
     else
    {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while (i < n1)
  {
    arr[k] = L[i];
    i++;
    k++;
  }

   while (j < n2)
   {
     arr[k] = R[j];
     j++;
     k++;
   }
 }
 public static void Mergesort(List<double> arr, int l, int r)
 {
    if (l < r)
    {
     int m = (l + r) / 2;
     Mergesort(arr, l, m);
     Mergesort(arr, m + 1, r);

     merge(arr, l, m, r);
   }
  }