A Benchmarking Program for various Sorting Algorithms writen in C.

SortingAlgsBenchmarks.c

// Sorting Algorithms Benchmarks v0.0
// Created by LaVanTien
// 02/01/2016 6:00 AM
// Compiled at C language - ISO C11
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define TEMPSIZE 10000
 
const int SIZEINT = sizeof (int);
const int SIZEBOOL = sizeof (bool);
 
void swap(int *, int *);
void burblesort(int *, const int);
void selectionsort(int *, const int);
void insertionsort(int *, const int, const int);
void quicksort(int *, const int, const int);
void quicksort_optimized(int *, const int, const int);
void merge(int *, const int, int *, const int, int *, const int);
void mergesort(int *, const int);
double time_burblesort(int *, const int);
double time_selectionsort(int *, const int);
double time_insertionsort(int *, const int);
double time_quicksort_good(int *, const int);
double time_quicksort_optimized(int *, const int);
double time_mergesort(int *, const int);
double maketest(const int, const int, int *, int *, int *, int *, int *, int *);
 
int main(void) {
    for ( ; ; ) {
        BACK_TOP:
        //system("clear"); // for Terminal (POSIX or MAC)
        system("cls"); // for CMD (DOS or Windows)
        puts("                       Sorting Algorithms Benchmarks v0.0                       ");
        puts("                             Presented by LaVanTien                             ");
        puts("////////////////////////////////////////////////////////////////////////////////");
        puts("// - An integer array of N members will be create automatically.              //");
        puts("// - User can chose MODE for array. There is totally 6 modes.                 //");
        puts("// - The value of each array's member will be random in range (0, N).         //");
        puts("// - This array will be use across all algorithms for best equality.          //");
        puts("// - If user enter an invalid input, the program will automatically restart.  //");
        puts("// WARNING: User should consider when N is larger than 100,000 because some   //");
        puts("//     Sorting Algorithm run pretty slow (which has O(N*N) runtime complexity)//");
        puts("// Sorting Algorithms implemented: Burble Sort, Selection Sort,               //");
        puts("//     Insertion Sort, 'Good' Quick Sort, 'Optimized' Quick Sort, Merge Sort  //");
        puts("////////////////////////////////////////////////////////////////////////////////");
        fputs("\nEnter N (0 < N < 1,000,001) (Enter 0 to exit): ", stdout);
        char tstr[TEMPSIZE];
        fgets(tstr, TEMPSIZE, stdin);
        int n = 1;
        if (sscanf(tstr, "%d", &n) != 1)
            goto BACK_TOP;
        if (n == 0)
            return 0;
        if (n > 1000000 || n < 0)
            goto BACK_TOP;
        int *v1 = malloc(n * SIZEINT);
        int *v2 = malloc(n * SIZEINT);
        int *v3 = malloc(n * SIZEINT);
        int *v4 = malloc(n * SIZEINT);
        int *v5 = malloc(n * SIZEINT);
        int *v6 = malloc(n * SIZEINT);
        puts("\nArray-Mode: (1)-Random. (2)-Random Unique. (3)-Reversed.\n\t    (4)-Partial Sorted. (5)-Sorted. (6)-Same.");
        fputs("Your choice (0 < choice < 7): ", stdout);
        fgets(tstr, TEMPSIZE, stdin);
        int mode = 1;
        if (sscanf(tstr, "%d", &mode) != 1) {
            free(v1);
            free(v2);
            free(v3);
            free(v4);
            free(v5);
            free(v6);
            goto BACK_TOP;
        }
        if (mode < 1 || mode > 6) {
            mode = 1;
            puts("Out of range! The default mode (1) will be used.");
        }
        printf("\n*** The array is successful created in %.3lfs ***\n", maketest(mode, n, v1, v2, v3, v4, v5, v6));
        puts("*** Sorting Algorithms is running. Please wait.. ***\n");
        double t1 = time_burblesort(v1, n - 1);
        double t2 = time_selectionsort(v2, n - 1);
        double t3 = time_insertionsort(v3, n - 1);
        double t4 = time_quicksort_good(v4, n - 1);
        double t5 = time_quicksort_optimized(v5, n - 1);
        double t6 = time_mergesort(v6, n);
        printf("*** Burble Sort:          | %.3lfs ***\n", t1);
        printf("*** Selection Sort:       | %.3lfs ***\n", t2);
        printf("*** Insertion Sort:       | %.3lfs ***\n", t3);
        printf("*** Quick Sort Good:      | %.3lfs ***\n", t4);
        printf("*** Quick Sort Optimized: | %.3lfs ***\n", t5);
        printf("*** Merge Sort            | %.3lfs ***\n", t6);
        fputs("\nQuit or Restart? (Please chose 0 or 1): ", stdout);
        fgets(tstr, TEMPSIZE, stdin);
        if (sscanf(tstr, "%d", &n) != 1) {
            free(v1);
            free(v2);
            free(v3);
            free(v4);
            free(v5);
            free(v6);
            goto BACK_TOP;
        }
        if (n == 0) {
            free(v1);
            free(v2);
            free(v3);
            free(v4);
            free(v5);
            free(v6);
            break;
        }
    }
    return 0;
}
 
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}
void burblesort(int *v, const int r) {
    for (int i = 0; i < r; i++)
        for (int j = r; j > i; j--)
            if (v[j] < v[i])
                swap(&v[i], &v[j]);
}
void selectionsort(int *v, const int r) {
    for (int i = 0; i < r; i++) {
        int min = v[i], posmin = i;
        for (int j = r; j > i; j--)
        if (v[j] < min) {
            min = v[j];
            posmin = j;
        }
        swap(&v[i], &v[posmin]);
    }
}
void insertionsort(int *v, const int l, const int r) {
    for (int i = l + 1; i <= r; i++) {
        int t = v[i];
        int j = i - 1;
        for ( ; v[j] > t && j >= 0; j--)
            v[j + 1] = v[j];
        v[j + 1] = t;
    }
}
void quicksort(int *v, const int l, const int r) {
    if (l >= r)
        return;
    int p = v[l + rand() % (r - l + 1)], i = l, j = r;
    do {
        while (v[i] < p)
            i++;
        while (v[j] > p)
            j--;
        if (i <= j) {
            if (i < j)
                swap(&v[i], &v[j]);
            i++;
            j--;
        }
    } while (i <= j);
    quicksort(v, l, j);
    quicksort(v, i, r);
}
void quicksort_optimized(int *v, const int l, const int r) {
    if (r - l < 38) {
        insertionsort(v, l, r);
        return;
    }
    int p = v[l + rand() % (r - l + 1)], i = l, j = r;
    do {
        while (v[i] < p)
            i++;
        while (v[j] > p)
            j--;
        if (i <= j) {
            if (i < j)
                swap(&v[i], &v[j]);
            i++;
            j--;
        }
    } while (i <= j);
    quicksort_optimized(v, l, j);
    quicksort_optimized(v, i, r);
}
void merge(int *v, const int n, int *left, const int nl, int *right, const int nr) {
    int i, j, k;
    i = j = k = 0;
    while (i < nl && j < nr) {
        if (left[i] < right[j]) {
            v[k] = left[i];
            k++;
            i++;
        }
        else {
            v[k] = right[j];
            k++;
            j++;
        }
    }
    for ( ; i < nl; i++) {
        v[k] = left[i];
        k++;
    }
    for ( ; j < nr; j++) {
        v[k] = right[j];
        k++;
    }
}
void mergesort(int *v, const int n) {
    if (n <= 1)
        return;
    int nl = n / 2;
    int nr = n - nl;
    int *left = malloc(nl * SIZEINT);
    int *right = malloc(nr * SIZEINT);
    for (int i = 0; i < nl; i++)
        left[i] = v[i];
    for (int i = nl; i < n; i++)
        right[i - nl] = v[i];
    mergesort(left, nl);
    mergesort(right, nr);
    merge(v, n, left, nl, right, nr);
    free(left);
    free(right);
}
double time_burblesort(int *v, const int r) {
    clock_t start = clock();
    burblesort(v, r);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}
double time_selectionsort(int *v, const int r) {
    clock_t start = clock();
    selectionsort(v, r);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}
double time_insertionsort(int *v, const int r) {
    clock_t start = clock();
    insertionsort(v, 0, r);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}
double time_quicksort_good(int *v, const int r) {
    clock_t start = clock();
    quicksort(v, 0, r);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}
double time_quicksort_optimized(int *v, const int r) {
    clock_t start = clock();
    quicksort_optimized(v, 0, r);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}
double time_mergesort(int *v, const int n) {
    clock_t start = clock();
    mergesort(v, n);
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}
double maketest(const int mode, const int n, int *v1, int *v2, int *v3, int *v4, int *v5, int *v6) {
    // 1-Random, 2-RandomUnique, 3-Reversed, 4-PartialSorted, 5-Sorted, 6-Same
    clock_t start = clock();
    srand(time(NULL));
    const int nt = n + 1;
    if (mode == 1)
        for (int i = 0; i < n; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = (rand() * rand()) % nt;
    else if (mode == 2) {
        bool *flag = calloc(nt, SIZEBOOL);
        for (int i = 0; i < n; i++) {
            for ( ; ; ) {
                int t = (rand() * rand()) % nt;
                if (!flag[t]) {
                    v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = t;
                    flag[t] = true;
                    break;
                }
            }
        }
        free(flag);
    }
    else if (mode == 3)
        for (int i = 0; i < n; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = n - i;
    else if (mode == 4) {
        const int k = rand() % (n / 2 + 1);
        const int j = k + n / 2 - 1;
        for (int i = 0; i < k; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = (rand() * rand()) % nt;
        for (int i = k; i <= j; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = i;
        for (int i = j + 1; i < n; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = (rand() * rand()) % nt;
    }
    else if (mode == 5)
        for (int i = 0; i < n; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = i;
    else if (mode == 6) {
        int t = (rand() % rand()) % nt;
        for (int i = 0; i < n; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = t;
    }
    else
        for (int i = 0; i < n; i++)
            v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = (rand() * rand()) % nt;
    clock_t end = clock();
    return (double)(end - start) / CLOCKS_PER_SEC;
}