/*
	Quick Sort versus Bin Sort demonstration
	written by Veselin Georgiev
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

const int MAXN = 1234567;
//const int MAXN = 12;

int mas[MAXN];

// Generate N random numbers
void rgen(int a[], int n)
{
	int i;

	srand(42);
	for (i = 0; i < n; i++) a[i] = rand()%19387;
}

// Swap two ints
static inline void swp(int *a, int *b) { int t = *a; *a = *b; *b = t; }

// QSort::partition
int partition(int a[], int l, int r, int x)
{
	int i, j;
	int t = l;
	for (i = l; i <= r; i++) if (a[i] < x) t++;
	swp(a+t, a+ ((l+r)/2));
	i = l;
	j = r;
	while (i < t || j > t) {
		while (i < t && a[i] < x) i++;
		while (j > t && a[j] >= x) j--;
		if (i < t || j > t) {
			swp(a+i, a+j);
			i++; j--;
		}
	}
	return t;
}

// QSort::recursion
void sort(int a[], int l, int r)
{
	int x, t;
	if (l >= r) return;
	x = a[(l + r) / 2];
	t = partition(a, l, r, x);
	sort(a, l, t-1);
	sort(a, t+1, r);
}

// QSort wrapper
void quick_sort(int a[], int n)
{
	sort(a, 0, n-1);
}

// Binary Sort (dynamically allocated temporary memory)
void bin_sort(int a[], int n)
{
	int div = 1, k, i, j, l;
	int *temp = malloc(sizeof(a[0])*n);
	for (int k = 0; k < 31; k++, div *= 2) {
		i = 0;
		j = n - 1;
		for (l = 0; l < n; l++) {
			if (a[l] / div % 2 == 0) 
				temp[i++] = a[l];
			else
				temp[j--] = a[l];
		}
		for (l = 0; l < i; l++)
			a[l] = temp[l];
		for (l = n-1; l > j; l--)
			a[i+n-1-l] = temp[l];
	}
	free(temp);
}


// main program (w/ test times)
int main(void)
{
	double start, runtime;

	rgen(mas, MAXN);

	start = clock();
	quick_sort(mas, MAXN); 
	runtime = (clock() - start) / CLOCKS_PER_SEC;
	printf("Quick Sort time: %.2lf\n", runtime);

	rgen(mas, MAXN);

	start = clock();
	bin_sort(mas, MAXN); 
	runtime = (clock() - start) / CLOCKS_PER_SEC;
	printf("Bin Sort time: %.2lf\n", runtime);

	return 0;
}