Comparison of Sorting Algorithms

Kategori: C , 04 Temmuz 2019 , JanFranco


Bu yazımızda sıralama algoritmalarını karşılaştıracağız. 1000, 10000, 100000 veriye sahip, elemanları rastgele olarak belirlenmiş arrayler oluşturacağız ve bu arrayleri bubble, insertion, selection, quick ve merge sort ile sıralayacağız. Tüm bu verileri elde ettiğimiz koda en aşağıdan erişebilirsiniz. Şimdi sonuçları inceleyelim:

  1000 10000 100000
BUBBLE 0.002s 0.374s 41.334s
INSERTION 0.001s 0.200s 15.939s
SELECTION 0.001s 0.218s 24.916s
QUICK <0s 0.006s 0.403s
MERGE <0s <0s 0.015s
Şimdi farklı boyutlarda arrayler oluşturup elemanlarını rastgele atayacağız. Daha sonra merge sort ile sıralayacağız. Sıralı array'i inverse() fonksiyonuna sokarak arrayin tersini alacağız. Yani sondaki eleman başa, baştaki eleman sona gelecek. Bu ters sıralanmış array'i tekrar sıralama algoritmalarını kullanarak sıralayacağız. inverse() fonksiyonu da en aşağıdaki kodda mevcut. Sonuçları inceleyelim:
  1000 10000 100000
BUBBLE <0s 0.328s 32.093s
INSERTION 0.002s 0.252s 28.110s
SELECTION 0.001s 0.176s 16.462s
QUICK 0.001s 0.087s 13.281s
MERGE <0s 0.001s 0.016s
Bu 5 sıralama algoritmasının time complexity değerlerini karşılaştıralım:
  WORST BEST
BUBBLE O(n^2) Ω(n)
INSERTION O(n^2) Ω(n)
SELECTION O(n^2) Ω(n^2)
QUICK O(n^2) Ω(n log(n))
MERGE O(n log(n)) Ω(n log(n))
Bu verileri elde etmek için kullandığımız kodlar:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 100000

int array[SIZE];

void random(){
    int i;
    for(i=0; i<SIZE; i++){
        array[i] = rand() % 100;
    }
}

void inverse(){
    int i, temp, change = SIZE;
    for(i=0; i<SIZE/2; i++){
        temp = array[i];
        array[i] = array[change-1];
        array[change-1] = temp;
        change--;
    }
}

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

int partition_(int arr[], int low, int high){
    int pivot = arr[high], j, i = low - 1, temp;
    for(j=low; j<=high-1; j++){
        if(arr[j] <= pivot){
            i++;
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;
}

void quick_sort(int arr[], int low, int high){
    if(low < high){
        int pi = partition_(arr, low, high);
        quick_sort(arr, low, pi-1);
        quick_sort(arr, pi+1, high);
    }
}

void insertion_sort(int arr[]){
    int i, j, element;

    for(i=1; i<SIZE; i++){
        element = arr[i];
        for(j=i-1; j>=0; j--){
            if(element > arr[j]){
                break;
            }
            arr[j+1] = arr[j];
            arr[j] = element;
        }
    }
}

void selection_sort(int arr[]){
    int i, j, min_index, temp;
    for(i=0; i<SIZE-1; i++){
        min_index = i;
        for(j=i+1; j<SIZE; j++){
            if(arr[j] < arr[min_index]){
                min_index = j;
            }
        }
        temp = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = temp;
    }
}

void bubble_sort(int arr[]){
    int i, j, temp;
    for(i=0; i<SIZE-1; i++){
        for(j=0; j<SIZE-1-i; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void display(){
    int i;
    for(i=0; i<SIZE; i++){
        printf("%d\n", array[i]);
    }
}

int main() {

    random();
    merge_sort(array, 0, SIZE);
    inverse();

    clock_t start = clock();
    merge_sort(array, 0, SIZE);
    clock_t end = clock();

    printf("TIME USED BY MERGE SORT = %f", ((double)(end-start)/CLOCKS_PER_SEC));

    return 0;
}


Sonraki Yazı: Linked List
Yorumlar

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