u/frymimori's sort vs introspective sort

sort-off.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define CUTOFF 16

void sorterQ(int * b, unsigned long a) {
	unsigned long c = a - 1;
	unsigned long d = 0;
	unsigned long e;
	int f;

	while (a != 0) {
		d = a;
		e = a;
		f = b[a];

		while (d != 0) {
			d--;

			if (b[d] > f) {
				f = b[d];
				e = d;
			}
		}

		b[e] = b[a];
		b[a] = f;
		a--;
	}

	return; //huh?
}

void exch(int a[], int l, int r) {
    int t = a[l]; a[l] = a[r]; a[r] = t;
}

void _downheap(int a[], int n, int k) {
    while (2*k <= n) {
        int j = k + k;
        if (j < n && a[j] < a[j+1]) j++;
        if (!(a[k] < a[j])) break;
        exch(a, k, j); k = j;
    }
}

void heapsort(int a[], int l, int r) {
    int n = r-l+1;
    int *heap = a+l-1;
    for (int k = n/2; k >= 1; k--)
        _downheap(heap, n, k);
    while (n > 1) {
        exch(heap, 1, n);
        _downheap(heap, --n, 1);
    }
}

void insertionsort(int a[], int l, int r) {
    for (int i = l; i <= r; i++) {
        int j = i; int v = a[j];
        while (j >= l && a[j - 1] > v) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = v;
    }
}

void medOf3(int a[], int l, int r) {
    int m = (l+r)/2;
    if (a[m] < a[l])
        exch(a, m, l);
    if (a[r] < a[m]) {
        exch(a, m, r);
        if (a[m] < a[l])
            exch(a, l, m);
    }
    exch(a, m, r);
}

int partition(int a[], int l, int r) {
    medOf3(a, l, r);
    int i = l - 1, j = r; int v = a[r];
    for (;;) {
        while (a[++i] < v);
        while (a[--j] > v) if (j == l) break;
        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, i, r);
    return i;
}

void _introsort(int a[], int l, int r, int depth) {
    if (depth == 0) {
        heapsort(a, l, r);
        return;
    }
    if (r - l < CUTOFF) {
        insertionsort(a, l, r);
        return;
    }
    depth--;
    if (r > l) {
        int i = partition(a, l, r);
        _introsort(a, l, i - 1, depth);
        _introsort(a, i + 1, r, depth);
    }
}

void introsort(int a[], int n) {
    int depth = floor(2*log(n));
    _introsort(a, 0, n - 1, depth);
}

void checksort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (a[i+1] < a[i]) {
            printf("Sort failed. at position %d: %d < %d\n", i, a[i+1], a[i]);
            return;
        }
    }
    puts("Sort successful.");
}

void timedsort(int a[], int n, char* algName, void (*sort)(int a[], int n)) {
    time_t start, end;
    double timing;
    printf("Algorithm: %s has started.\n", algName);
    start = clock();
    sort(a, n);
    end = clock();
    timing = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("Algorithm: %s processed %d items in %f seconds\n", algName, n, timing);
    checksort(a, n);
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        puts("Error: You must supply the number of items to sort.");
        printf("Usage: %s <N>\n", argv[0]);
        return -1;
    }
    srand(time(0));
    int n = atoi(argv[1]);
    int *ts = malloc(sizeof(int) * n);
    int *ts2 = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        int p = rand() % RAND_MAX;
        ts[i] = p;
        ts2[i] = p;
    }
    timedsort(ts, n, "Introspective sort", &introsort);
    timedsort(ts, n, "u/frymimori sort", &sorterQ);
    return 0;
}

/*

max@MaxGorenLaptop:/mnt/c/Users/mgoren$ gcc -O2 introspectivesort.c -o introsort -lm
max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./introsort 1000 ; ./introsort 10000 ; ./introsort 100000
Algorithm: Introspective sort has started.
Algorithm: Introspective sort processed 1000 items in 0.000052 seconds
Sort successful.
Algorithm: u/frymimori sort has started.
Algorithm: u/frymimori sort processed 1000 items in 0.000194 seconds
Sort successful.
Algorithm: Introspective sort has started.
Algorithm: Introspective sort processed 10000 items in 0.000541 seconds
Sort successful.
Algorithm: u/frymimori sort has started.
Algorithm: u/frymimori sort processed 10000 items in 0.016719 seconds
Sort successful.
Algorithm: Introspective sort has started.
Algorithm: Introspective sort processed 100000 items in 0.005521 seconds
Sort successful.
Algorithm: u/frymimori sort has started.
Algorithm: u/frymimori sort processed 100000 items in 1.405508 seconds
Sort successful.
max@MaxGorenLaptop:/mnt/c/Users/mgoren$

*/