Algoritma Dersleri – Merge Sort

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Merge Sort algoritmasını anlatmaya çalışacağız.

Artık verimsiz olarak adlandırdığımız N^2’lik Sıralama Algoritmalarını bitirmiş ve temel oluşturmuş bir şekilde verimli Sıralama Algoritması olan Merge Sort Algoritmasına giriş yapacağız.

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ıyse 2. while kalan bütün L dizisini cevaba aktarıyor. Aynı şekilde R dizisinde eleman kaldıyse 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.

Mergesort 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 özyinelemeli (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.

Şimdi bazı popüler dillerdeki Merge Sort kodlarına bakalım:

C++

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);
    }
}

Java

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

Python

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m
 
   
    L = [0] * (n1)
    R = [0] * (n2)
 
   
    for i in range(0 , n1):
        L[i] = arr[l + i]
 
    for j in range(0 , n2):
        R[j] = arr[m + 1 + j]
 
   
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2 :
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
   
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
   
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 

def mergeSort(arr,l,r):
    if l < r:
 
        
        m = (l+(r-1))/2
 
        
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

Okuduğunuz için teşekkür ederim umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.