sort.c

.gitignore

a.out

Insertion vs quick sort.png

sample.csv

sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>

// Max size of input
#define SIZE 32

// Number of times each experiment is repeated
#define TIMES 16

static void swap(int *i, int *j) {
    int temp = *i;
    *i = *j;
    *j = temp;
}

// Insertion sort
void i_sort(int *a, size_t size) {
    // (0 i] is already sorted
    for (size_t i = 1; i < size; i++) {

        // Insert a[j] into (0 j]
        for (int j = i; j > 0; j--) {
            if (a[j - 1] > a[j]) {
                swap(&a[j - 1], &a[j]);
            }
        }
    }
}

// Quick sort
size_t partition(int a[], size_t low, size_t high) {
    const int pivot = a[low];
    size_t offset = low;

    for (size_t i = low + 1; i < high; i++) {
        if (a[i] < pivot) {
            swap(&a[offset], &a[i]);
            offset++;
        }
    }
    return offset + 1;
}

void quick_sort(int a[], size_t low, size_t high) {
    if (low < high) {
        int pivot = partition(a, low, high);
        quick_sort(a, low, pivot - 1);
        quick_sort(a, pivot + 1, high);
    }
}

void q_sort(int a[], size_t size) {
    return quick_sort(a, 0, size);
}

/* void static print(int *a, size_t size) { */
/*     for (size_t i = 0; i < size; i++) { */
/*         printf("%d ", a[i]); */
/*     } */
/*     printf("\n"); */
/* } */

long timeit(void (*action)(int[], size_t), int a[], size_t size) {
    struct timespec tsi, tsf;

    clock_gettime(CLOCK_MONOTONIC, &tsi);
    action(a, size);
    clock_gettime(CLOCK_MONOTONIC, &tsf);

    double elaps_s = difftime(tsf.tv_sec, tsi.tv_sec);

    // Just return the ns if the total time is less than 1s
    assert(elaps_s == 0);

    return tsf.tv_nsec - tsi.tv_nsec;
}


int main() {

    int nums[SIZE], c1[SIZE], c2[SIZE];

    srand(time(NULL)); // should only be called once
    for (size_t i = 0; i < SIZE; i++) {
        nums[i] = rand(); // [0, RAND_MAX]
    }

    printf("size, insertion sort, quick sort\n");

    for (int range = 0; range <= SIZE; range++) {

        double t1 = 0, t2 = 0;

        for(int times = 0; times < TIMES; times++) {

            // Copying the whole buffer might be even simpler than range
            memcpy(c1, nums, sizeof nums[0] * SIZE);
            memcpy(c2, nums, sizeof nums[0] * SIZE);

            t1 += timeit(i_sort, c1, range);
            t2 += timeit(q_sort, c2, range);
        }

        printf("%d, %f, %f\n", range, t1/TIMES, t2/TIMES);
    }

    return 0;
}