C Programlama Merge Sort

Merge Sort Nasıl Çalışır?

Divide and Conquer yaklaşımının en temel örneklerinden biri olan Merge Sort, sıralayacağımız diziyi her seferinde ikiye bölüp ayrı ayrı sıraladıktan sonra birleştirme mantığına dayanmaktadır. Biraz daha ayrıntılı anlatmam gerekirse: Algoritmamız iki fonksiyondan oluşuyor. Birincisi girilen diziyi ikiye bölüp ayrı ayrı sıralamayı sağlarken diğeri sıralanmış iki diziyi birleştirmemizi sağlıyor.

Kaba bir kod paylaştıktan sonra algoritma analizini yapmaya devam edelim.

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    i = 0;
    j = 0;
    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++;
    }
}
 
 
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

Merge Sort Analizi

Merge dediğimiz fonksiyon kendi içinde sıralanmış L[] ve R[] dizilerini birleştiriyor. Ancak burdaki önemli ayrıntı dizileri birleştirirken sıralama bozulmadan birleşiyor. Yani merge fonksiyonu tamamlandığında L[] ve R[] dizilerinin toplam uzunluğunda sıralı bir dizi oluşuyor. Nasıl birleştirdiği hakkında elimden geldiğince açıklamaya çalışayım.

Birleştirme işleminin 3 while döngüsüyle yapan Merge fonksiyonu, 1. while döngüsünde L ve R dizisini beraber gezerek öncelikli olarak küçük elemanı cevabımızın saklandığı arr dizisine atıyor. Daha sonra elimizde fazladan L veya R dizisinde eleman kalmış olabilir ancak biz biliyoruz ki 1. while tamamlanınca L ve R dizilerinden en az birisi tamamen gezilmiş ve cevaba aktarılmıştır. Eğer L dizisinde fazlalık kaldıysa 2. while kalan bütün L dizisini cevaba aktarıyor. Aynı şekilde R dizisinde eleman kaldıysa 3. while R’nin tamamının cevaba atıyor. Böylelikle merge fonksiyonu tamamlandığında L ve R dizisi sıralı bir şekilde arr dizisinde birleşmiş oluyor.

Merge sort fonksiyonundan bahsetmek gerekirse, her seferinde gelen dizinin önce ilk yarısını sıralıyor daha sonra ikinci yarısını sıralıyor. Böylelikle elinde iki tane sıralı dizi oluyor. Daha sonra az önce anlattığımız Merge fonksiyonunu kullanarak bu iki sıralı diziyi doğru bir şekilde birleştiriyor.

 Karmaşıklık Hesabı

Bu öz yinelemeli (recursive) bir fonksiyon olduğu için sürekli kendini çağırarak hep diziyi ikiye bölüyor. Böylelikle en fazla log2(N) kere bölme işlemi yapılmış oluyor. Her bölünmüş dizinin Merge işlemi içinde dizinin uzunluğu olan N işlem yapıldığı için bu algoritmanın karmaşıklık maliyeti büyük O notasyonunda O(N * log(N)) oluyor. Önceki gördüğümüz sıralama algoritmalarına nazaran çok daha verimli olan Merge sort sayesinde çok kısa sürede 1 000 000 uzunluğundaki dizileri bile sıralayabiliyoruz.

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void merge(int dizi[],int ilk,int orta ,int son);
void mergesort(int dizi[],int ilk,int son)
{
 if(son>ilk)
 {
  int orta=(ilk+son)/2;
   mergesort(dizi,ilk,orta);
   mergesort(dizi,orta+1,son);
   merge(dizi,ilk,orta,son);
 }
}
void merge(int dizi[],int ilk,int orta,int son)
{
 int gecici[1000];
 int ilk1=ilk,son1=orta;
 int ilk2=orta+1,son2=son;
 int index=ilk1;
 for(;(ilk1<=son1) && (ilk2<=son2);index++)
 {
  if(dizi[ilk1]<dizi[ilk2])
  {gecici[index]=dizi[ilk1];
  ilk1++;}//gecici diziye elemanlar sıralı şekilde atılmaktadır.Elemanlar bura sirayla atılır ilk1 den başlayıp son1 kadar ilerlemektedir.
  else{
   gecici[index]=dizi[ilk2];
   ilk2++;
  }
 }
 for(;ilk1<=son1;ilk1++,index++)
 {
  gecici[index]=dizi[ilk1]; //birinci dizini alt elmeanları bıtmısse iki diziyi kendi içerisinde birleştiriyoruz.
 }
 for( ;ilk2<=son2;ilk2++,index++)
 {//ikinci dizin alt elmanları bitmişse ikinci diziyide güzel bir şekilde sıralamktayız.
  gecici[index]=dizi[ilk2];
 }
 for(index=ilk;index<son;index++)
 {
  dizi[index]=gecici[index];//en son şekildede diziyi güzel bir şekilde sıralamktayız.
 }
}