Algorithms Complexity

algorithmComplexity.c

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

#define VAL_MAX 500
#define SPACING 8
#define MAX_SHOWING 50

//PROTOTYPES OF THE FUNCTIONS
void askUserData(int*);
int **createDinamicArray(int);

void fillArrWRandVar(int**,int);
void showArrFirst(int*,int);
void showArrFinal(int*, int);
void showArr(int*,int);

void mergeSort(int*,int,int);
void merge(int*,int, int, int);

double insertionSort(int*,int);

void selectionSort(int*,int,int);
int buscarPosMinimo(int*,int,int);

double bubbleSort(int*,int);


void showMsg(int);
void showTime(double,char*);
void freeMemory(int**);

void initMergeSort(int*,int);
void initInsertionSort(int*,int);
void initBubbleSort(int*,int);
void initSelectionSort(int*,int);


//MAIN FUNCTION
int main(int argc, char const *argv[])
{
    srand(time(NULL));

    int n, **arrElements;
    askUserData(&n);
    arrElements = createDinamicArray(n);
    fillArrWRandVar(arrElements,n);

    printf("Array disordered.\n");
    showArrFirst(arrElements[0],n);

    initInsertionSort(arrElements[0],n);
    initBubbleSort(arrElements[1],n);
    initSelectionSort(arrElements[2],n);
    initMergeSort(arrElements[3],n);

    freeMemory(arrElements);
    return 0;
}


//INIT FUNCTIONS
void initMergeSort(int *arr,int n){
    double time_spent = 0.0;
    clock_t t0 = clock();

    mergeSort(arr,0,n);

    clock_t t1 = clock();
    time_spent+=(double)(t1-t0) / CLOCKS_PER_SEC;

    showTime(time_spent,"Merge Sort");
    printf("Array ordered.\n");
    showArr(arr,n);

}

void initInsertionSort(int *arr,int n){
    double time_spent = insertionSort(arr,n);

    showTime(time_spent,"insertion sort");
    printf("Array ordered.\n");
    showArr(arr,n);
}

void initBubbleSort(int *arr,int n){
    double time_spent = bubbleSort(arr,n);

    showTime(time_spent,"bubble sort");
    printf("Array ordered.\n");
    showArrFirst(arr,n);
}

void initSelectionSort(int *arr,int n){
    double time_spent = 0.0;
    clock_t t0 = clock();

    selectionSort(arr,n,0);

    clock_t t1 = clock();
    time_spent+=(double)(t1-t0) / CLOCKS_PER_SEC;


    showTime(time_spent,"selection sort");
    printf("Array ordered.\n");
    showArr(arr,n);
}

//ALGORITHMS
    //SELECTION SORT//
void selectionSort(int *arr,int n,int dd){
    int posMin;
    if (dd<n){
        posMin = buscarPosMinimo(arr,n,dd);

        int aux = arr[dd];
        arr[dd] = arr[posMin];
        arr[posMin] = aux;

        selectionSort(arr,n,dd+1);
    }
    
}
int buscarPosMinimo(int *arr,int n, int dd){
    int posMin = dd;
    int min = arr[dd];
    int i;
    for (i = dd+1; i < n; i++){
        if(arr[i]<min){
            min = arr[i];
            posMin = i;
        }}
    
    return posMin;
    
}

    //BUBBLE SORT//
double bubbleSort(int *arr,int n){
    double time_spent = 0.0;

    clock_t t0 = clock();

    int i, aux, ordenado = 0;
    while (!ordenado){
        ordenado=1;
        for (i = 0; i < n-1; i++){

            if(arr[i]>arr[i+1]){
                aux = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = aux;
                ordenado = 0;
            }
        }
    }

    clock_t t1 = clock();
    time_spent+=(double)(t1-t0) / CLOCKS_PER_SEC;

    return time_spent;
}

    //MERGE SORT//
void mergeSort(int *arr,int p, int r){
    int q;
    

    if(p<r){
        q=p + (r - p) / 2;
        mergeSort(arr,p,q);
        mergeSort(arr,q+1,r);
        merge(arr,p,q,r);
    }
}
void merge(int *arr,int p, int q, int r){
    int i,j,k;
    
    int n1 = q-p+1;
    int n2 = r-q;

    int left[n1+1], right[n2+1];

    for (i = 0; i < n1; i++)
        left[i] = arr[p+i];
    
    for (j = 0; j < n2; j++)
        right[j] = arr[q+j+1];

    left[i] = VAL_MAX;
    right[j] = VAL_MAX;

    i = j = 0;

    for(k = p; k<r+1 ;k++){
        if(left[i] <= right[j]){
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
    }
}

    //INSERTION SORT
double insertionSort(int *arr,int n){
    int j,i,key;
    double time_spent = 0.0;

    clock_t t0 = clock();

    for (j = 1; j < n; j++){
        i =j;
        key = arr[j];
        while (i > 0 && arr[i-1] > key){
            arr[i] = arr[i-1];
            i--;
        }
        arr[i] = key;
    }

    clock_t t1 = clock();
    time_spent+=(double)(t1-t0) / CLOCKS_PER_SEC;

    return time_spent;
}

//MISCELANEOUS THINGS
void askUserData(int *n){
    printf("How many elements?: ");
    scanf("%d",n);
}

int **createDinamicArray(int n){
    int **array;
    array = (int**)malloc(sizeof(int*)*4);
    if(array == NULL){
        showMsg(0);
        exit(-1);
    }

    for (int i = 0; i < 4; i++){
        array[i] = (int*)malloc(sizeof(int)*n);
         if(array[i] == NULL){
            showMsg(0);
            exit(-1);
        }
    }

    return array;
}

void fillArrWRandVar(int **arr,int n){
    for (int i = 0; i < n; i++){
        int randValue = (rand()%99)+1;
        arr[0][i] = randValue;
        arr[1][i] = randValue;
        arr[2][i] = randValue;
        arr[3][i] = randValue;
    }
}

    //SHOWING ARRAYS//
void showArrFirst(int *arr, int n){
    int i, showN = n;
    int op = 1;

    if(n > MAX_SHOWING){
        printf("Mostrar elementos?(Si: 1 | No: 0): ");
        scanf("%d",&op);
        showN = MAX_SHOWING;
    } 

    for (i = 0; i < showN && op!= 0; i++) {
        printf("Num. [%d]: %d\n", i+1, arr[i]);
    }
    printf("\n\n");
}

void showArrFinal(int *arr, int n){
    int i, showN = n;

    int op = 1;

    if(n > MAX_SHOWING){
        printf("Mostrar elementos?(Si: 1 | No: 0): ");
        scanf("%d",&op);
        showN = MAX_SHOWING;
    } 

    for (i = 1; i <= showN && op != 0; i++) {
        printf("Num. [%d]: %d\n", i, arr[i]);
    }
    
    printf("\n\n");
}

void showArr(int *arr, int n){
    int i, showN = n;

    int op = 1;

    if(n > MAX_SHOWING){
        printf("Mostrar elementos?(Si: 1 | No: 0): ");
        scanf("%d",&op);
        showN = MAX_SHOWING;
    } 

    for (i = 0; i < showN && op != 0; i++) {
        printf("Num. [%d]: %d\n", i+1, arr[i]);
    }
    printf("\n\n");
}

void showTime(double time_spent, char *algorithm){
    printf("The computing time it takes to the %s is [%f]s\n", algorithm,time_spent);
    printf("----------------------------------------------------\n\n");
}

void showMsg(int n){
    char *errors[] = {
        "Memory Error allocating the array...",
        "The memory has been sucessfully liberated"
    };
    printf("Msg: [%s]",errors[n]);
}

void freeMemory(int **arr){
    for (int i = 0; i < 4; i++)
        free(arr[i]);
    
    free(arr);
    showMsg(1);
}