Merge Sort

Kategori: C , 02 Temmuz 2019 , JanFranco


Merge sort algoritması, verilen diziyi parçalara ayırır ve bu parçaları kendi halinde sıralayıp birleştirerek, sıralanmış diziyi oluşturmuş olur. Hızlı ve etkilidir ancak yer problemi vardır. Kodu incelerken göreceksiniz, her bir merge fonksiyonu adımında 2 yeni dizi oluşturmakta. Algoritma recursive bir şekilde çalışıyor ve verilen diziyi ikiye bölüyor. Bu ikiye bölünen dizileri sadece bir eleman kalana kadar ikiye bölerek parçalara ayırıyor. Daha sonra parçalara ayrılmış elemanları, sıralayarak geri grupluyor. Recursive bir algoritma olduğundan anlaşılması ilk başta zor olabiliyor. Örnek bir dizi ve sırasıyla hangi sonuçlar açığa çıkıyor resim üzerinden görelim:
C implementasyonu:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20

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 merge_sort(int arr[], int l, int r){
    if(l < r){
        int m = l+(r-l)/2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

void print_array(int arr[]){
    int i;
    for(i=0; i<N; i++){
        printf("%d  ", arr[i]);
    }
    printf("\n");
}

int main() {

    int arr[N], i;
    srand(time(NULL));

    for(i=0; i<N; i++){
        arr[i] = rand() % N;
    }
    print_array(arr);
    merge_sort(arr, 0, N-1);
    printf("\nAfter sorting:\n");
    print_array(arr);

    return 0;
}


Sonraki Yazı: Hash Table
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın