Quick Sort [with and without randomized element]

QuickSort.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 initQuickSort(int*,int);
void quickSort(int*,int,int);
int partition(int*,int,int);

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

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

void mergeSort(int*,int,int);
void merge(int*,int,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);

        //ORDER THE ELEMENTS WITH MERGE SORT
        //FOR THE WORST CASE
    //mergeSort(arrElements,0,n);

    printf("Array disordered.\n");
    showArr(arrElements,n);

    initQuickSort(arrElements,n);

    freeMemory(arrElements);
    return 0;
}


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

    quickSort(arr,0,n-1);

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

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

}

//ALGORITHMS
    //QUICK SORT
void quickSort(int *A,int p,int r){
    if (p<r){
        int q = partition(A,p,r);
        
        quickSort(A,p,q-1);
        quickSort(A,q+1,r);
    }
}

int partition(int *A,int p,int r){
    int x = A[r];
    int i = p-1;
    for (int j = p; j < r; j++){
        if(A[j] <= x){
            i++;
            int aux = A[i];
            A[i] = A[j];
            A[j] = aux;
        }
    }
    int aux = A[i+1];
    A[i+1] = A[r];
    A[r] = aux;

    return i+1;
}

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

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

    return array;
}

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

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]\n",errors[n]);
}

void freeMemory(int *arr){
    free(arr);
    showMsg(1);
}

//MERGE SORT FOR ORDENING FIRST THE ARRAY
    //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 ;k++){
        if(left[i] <= right[j]){
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
    }
}

quickSortRandomized.c

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

#define VAL_MAX 500
#define MAX_SHOWING 50

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

void initRandomizedQuickSort(int*,int);
void RandomizedQuickSort(int*,int,int);
int randomizedPartition(int*,int,int);
int partition(int*,int,int);

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

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

void mergeSort(int*,int,int);
void merge(int*,int,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);
    
        //ORDER THE ELEMENTS WITH MERGE SORT
        //FOR THE WORST CASE
    //mergeSort(arrElements,0,n);

    printf("Array disordered.\n");
    showArr(arrElements,n);

    initRandomizedQuickSort(arrElements,n);

    freeMemory(arrElements);
    return 0;
}


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

    RandomizedQuickSort(arr,0,n-1);

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

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

}

//ALGORITHMS
    //QUICK SORT
void RandomizedQuickSort(int *A,int p,int r){
    if (p<r){
        int q = randomizedPartition(A,p,r);
        
        RandomizedQuickSort(A,p,q-1);
        RandomizedQuickSort(A,q+1,r);
    }
}

int randomizedPartition(int *A,int p, int r){
    int i = rand()%(abs(r-p)) + (p<r?p:r);
    int aux = A[r];
    A[r] = A[i];
    A[i] = aux;

    return partition(A,p,r);
}

int partition(int *A,int p,int r){
    int x = A[r];
    int i = p-1;
    for (int j = p; j < r; j++){
        if(A[j] <= x){
            i++;
            int aux = A[i];
            A[i] = A[j];
            A[j] = aux;
        }
    }
    int aux = A[i+1];
    A[i+1] = A[r];
    A[r] = aux;

    return i+1;
}

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

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

    return array;
}

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

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]\n",errors[n]);
}

void freeMemory(int *arr){
    free(arr);
    showMsg(1);
}

//MERGE SORT FOR ORDENING FIRST THE ARRAY
    //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 ;k++){
        if(left[i] <= right[j]){
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
    }
}