Skip to main content
Birleştirme Sıralaması (Merge Sort)

Birleştirme Sıralaması (Merge Sort Algorithm)

Merhabalar , bu yazımızda sıralama algoritmalarından birisi olan Birleştirme Sıralaması (Merge Sort) ’dan bahsedeceğiz .

Birleştirme Sıralaması (Merge Sort Algorithm) Nedir?

Birleştirme Sıralaması (Merge Sort Algorithm) , Quick Sort gibi Divide & Conquer ( Böl ve Yönet ) mantığıyla çalışan bir algoritmadır. Başlangıçtaki diziyi her bir parça 2 eleman kalana kadar dizinin elemanlarını 2 parçaya ayırır . Daha sonra kalan kısımlar kendi içlerinde sıralanır ve dizi tekrar birleştirilir . En nihayetinde elde etmiş olduğumuz dizi sıralanmış bir dizidir.

Yardımcı Alan: O (n)
Algoritmik Paradigma: Böl ve Yönet
Yerinde Sıralama: Genelde hayır
İstikrarlı: evet

Birleştirme Sıralaması (Merge Sort)
Birleştirme Sıralaması (Merge Sort)

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

Yukarıda ki şemayı incelersek , elimizde ; 38 , 27 , 43 , 3 , 9 , 82 , 10 sayılarından oluşan 7 elemanlı bir dizi var.

  1. Adım : Elimizdeki diziyi ikiye bölelim (38,27,43,3) , (9,82,10)
  2. Adım : Oluşan iki diziyi tekrar ikiye bölelim (38,27) (43,3) , (9,82) ,(10)
  3. Adım : Oluşan dizilerimizi tekrar ikiye bölünce (38)(27) , (43)(3) , (9)(82) ,(10) kaldı .
  4. Adım : Elimizde kalan son ikilik dizileri kendi arasında sıralayıp tekrar birleştirelim (27,38) , (3,43) , (9,82) ,(10)
  5. Adım : Elimizde 4 adet parça var ikişer ikişer sıralayarak tekrar birleştirelim (3,27,38,43) , (9,10,82)
  6. Adım : Son iki dizimizide sıralayıp tekrar birleştirirsek ; (3,9,10,27,38,43,82) şeklinde dizimizi küçükten büyüğe doğru sıralamış oluruz.

C dilinde Merge Sort

/* C ile Merge Sort */
#include<stdlib.h> 
#include<stdio.h> 
  
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    /* L ve R adında iki adet boş dizi oluştur */
    int L[n1], R[n2]; 
  
    /* Veriyi L ve R dizilerinde sakla */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    /* Birleşmiş olan L[] ve R[] dizilerini tekrar arr[] dizisine atayın */
    i = 0; // İlk alt dizinin ilk dizini 
    j = 0; // İkinci alt dizinin ilk dizini
    k = l; // Birleştirilmiş dizinin ilk dizini
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    /* Kalan herhangi bir L[] dizisi varsa , kopyalayın */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    /* Kalan herhangi bir R[] dizisi varsa , kopyalayın */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
/* Sıralanacak arr[] dizisinin sol dizisi L[] sağ dizisi R[]'dir */
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        
        int m = l+(r-l)/2; 
  
        // Birinci ve ikinci yarıları sırala
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
} 
  

/* Diziyi ekrana bastır */
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
  
/* Programı test etmek için main fonksiyon */
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Verilen Dizi : \n"); 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    printf("\nSıralanmış Dizi :  \n"); 
    printArray(arr, arr_size); 
    return 0; 
} 

Çıktı :

Verilen dizi
12 11 13 5 6 7

Sıralanan dizi
5 6 7 11 12 13

Kodumuzu Açıklayalım..

mergeSort(int arr[], int l, int r) fonksiyonunu incelersek ; her seferinde gelen diziyi öncelikle ilk yarısını alıp daha sonra ikinci yarısını alıyor ve elinde 2 tane sıralı dizi oluyor. Daha sonra merge(int arr[], int l, int m, int r) fonksiyonu ile birleştiriyor.

Karmaşıklık Hesabı

Yazılan C/C++ koduna bakarsak ; yazılan fonksiyon öz yinelemeli (recursive) olduğu için sürekli kendisini çağırarak her seferinde diziyi ikiye bölüyor . Bu sayede max. log2(n) kez bölme işlemi yapmış oluruz. Önceki gördüğümüz sıralama algoritmalarını nazaran Merge Sort çok daha verimlidir. Merge Sort sayesinde çok uzun dizileri bile çok kısa süre içerisinde sıralayabiliriz.

Sıralama algoritmaları ile ilgili daha fazla yazımızı okumak için http://kodlar.net/ ‘ i takip edebilirsiniz.Merge Sort hakkında daha fazla bilgi ve daha fazla dökümana sahip olmak için burayı ziyaret edebilirsiniz.

Emre Sualp

Kocaeli Üniversitesi Bilgisayar Mühendisliği 4. sınıf öğrencisiyim .Java , Javascript ve Android programlama ile ilgileniyorum.Bildiklerimi aktarmak ve yeni öğrendiğim konuları pekiştirmek için yazılarımı sizlerle paylaşacağım.

One thought to “Birleştirme Sıralaması (Merge Sort Algorithm)”

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir