#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int *shuffle(int *a, int size) {
	int i, j, ai;
	for (i = size - 1; i > 0; i--) {
		j = rand() % i;
 		ai = a[i];a[i] = a[j];a[j] = ai;
	}
	return a;
}
int *_ia(int first, int last) {
	int i, len = 1 + last - first, *a;
	if (last < first || len < 1) return 0;
	
	a = malloc(sizeof (int) * len);
	for (i = 0; i < len; i++) a[i] = first + i;
	return a;
}
int icmp(const void *a, const void *b){
    return *(int *)a - *(int *)b;
}

void *dup(const void *src, size_t nel, size_t width) {
	void *dst = malloc(nel * width);
	memcpy(dst, src, nel * width);
	return dst;
}
clock_t check(
	void (*sort)(void *, size_t, size_t, int (*)())
	, const void *src, size_t nel, size_t width
	, int (*compar)(const void *, const void *)
) {
	clock_t start, end;
	void *base = dup(src, nel, width);
	start = clock();
	sort(base, nel, width, compar);
	end = clock();
	free(base);
	return (end - start);
}
void swap(char *a, char *b, unsigned width) {
	char tmp;
	if (a != b) {
		while (width--) {
			tmp = *a;
			*a++ = *b;
			*b++ = tmp;
		}
	}
}
void bubble_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
	int i, j;
	for (i = 0; i < nmemb - 1; i++) {
		for (j = i + 1; j < nmemb; j++) {
			if (compar(base + size * i, base + size * j) > 0) {
				swap(base + size * i, base + size * j, size);
			}
		}
	}
}
void comb_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
	int h = nmemb * 10 / 13, i, swaps;
	for (;;) {
		swaps = 0;
		for (i = 0; i + h < nmemb; i++) {
			if (compar(base + size * i, base + size * (i + h)) > 0) {
				swap(base + size * i, base + size * (i + h), size);
				swaps++;
			}
		}
		if (h == 1) {
			if (swaps == 0) break;
		} else {
			h = h * 10 / 13;
		}
	}
}
int main() {
	srand(time(NULL));
	size_t nel = 25000, width = sizeof (int);
	int *org = shuffle(_ia(0, nel - 1), nel);
	printf("qsort: %f\n", (double)check(qsort, org, nel, width, icmp) / CLOCKS_PER_SEC);
	printf("bsort: %f\n", (double)check(bubble_sort, org, nel, width, icmp) / CLOCKS_PER_SEC);
	printf("csort: %f\n", (double)check(comb_sort, org, nel, width, icmp) / CLOCKS_PER_SEC);
	return 0;
}