sorting

I benchmarked some sorting algorithms in c.

Env: wsl2, ubuntu 22.04, clang 17.0.0 CPU: i7-10875H, RAM: Unlimited

No optimization

Algorithm	Bubble Sort(s)	Insertion Sort(s)	Quick Sort(s)	qsort(s)
10000	0.234375	0.234375	0.000000	0.000000
30000	2.187500	0.468750	0.000000	0.000000
50000	5.984375	1.390625	0.000000	0.000000
100000	24.156250	5.250000	0.000000	0.000000
500000			0.062500	0.015625
1000000			0.140625	0.031250
2000000			0.250000	0.062500

-O3

Algorithm	Bubble Sort(s)	Insertion Sort(s)	Quick Sort(s)	qsort(s)
100000	9.953125	1.234375	0.000000	0.000000
500000		33.296875	0.031250	0.015625
1000000			0.078125	0.015625
2000000			0.140625	0.062500

The testing code:

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

int len = 10000;

int randint(int min, int max) {
    return rand() % (max - min + 1) + min;
}

void randarr(int* arr) {
    for (int i = 0; i < len; i++) {
        arr[i] = randint(0, len);
    }
}

void bubble(int* arr, int start, int len) {
    int i, j, tmp;
    for (i = 0; i < len; i++) {
        for (j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

void insertion(int* arr, int start, int len) {
    int i, j, tmp;
    for (i = 1; i < len; i++) {
        tmp = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > tmp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tmp;
    }
}

void quick(int* arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        int j, tmp;
        for (j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }
        tmp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = tmp;
        quick(arr, low, i);
        quick(arr, i + 2, high);
    }
}

double benchmark(void (*func)(int*, int, int), int* arr, int low, int len) {
    clock_t start = clock();
    func(arr, low, len);
    clock_t end = clock();
    double time = (double)(end - start) / CLOCKS_PER_SEC;
    return time;
}

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

int main() {
    int arr[len];
    srand(time(NULL));
    randarr(arr);
    printf("Bubble sort: %f\n", benchmark(bubble, arr, 0, len));
    randarr(arr);
    printf("Insertion sort: %f\n", benchmark(insertion, arr, 0, len));
    randarr(arr);
    printf("Quick sort: %f\n", benchmark(quick, arr, 0, len));

    clock_t start = clock();
    qsort(arr, len, sizeof(int), cmpfunc);
    clock_t end = clock();
    double time = (double)(end - start) / CLOCKS_PER_SEC;
    printf("qsort: %f\n", time);

    return 0;
}