#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<assert.h>

static inline void
SWAP (int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

static inline int
mid_point(int a, int b, int c)
{
	if (a < b) {
		if (b < c)
			return b;
		else if (a < c)
			return c;
		else 
			return a;
	} else {
		if (a < c)
			return a;
		else if (b < c)
			return c;
		else 
			return b;
	}
}

void
selectsort(int *v, int s0, int e0)
{
	int i,j;
	int m;
	int size = e0-s0+1;
	v += s0;
	for (i=0; i<size; i++) {
		m = i;
		for (j=i+1; j<size; j++) {
			if (v[m] > v[j])
				m = j;
		}
		if (m!=i)
			SWAP(&v[i],&v[m]);
	}
	return;
}

void
quicksort(int *v, int s0, int e0)
{
	int p;
	int s=s0, e=e0;
#if 0
	if (e<=s) return;
	if (e-s<5) {
		selectsort(v,s0,e0);
		return;
	}
#else
	if (e<=s) return;
#endif

	//p = (v[s]+v[(s+e)/2]+v[e])/3;
	p = mid_point(v[s],v[e],v[(s+e)/2]);

	while (1) {
		 while (v[s]<p) s++;
		 while (p<v[e]) e--;

		 if (!(s<e)) break;
		 SWAP(&v[s], &v[e]);
		 s++; e--;
	}
	assert(e+1==s || s==e);

	quicksort(v, s0, e);
	quicksort(v, e+1, e0);
	return;
}

static void
print_array(int *v, int size)
{
	int i;
	printf("[");
	for (i=0; i<size; i++) {
		printf("%s%4d", (i%10==0)? "\n  ":" ", v[i]);
	}
	printf("]\n");
}

static int
check_sort(int *v, int size)
{
	int i;
	for (i=0; i<size-1; i++) {
		if (v[i] > v[i+1])
			return 0;
	}
	return 1;
}

void
random_initialize(int *v, int size, int min, int max)
{
	int i;
	int diff = max-min+1;

	for (i=0; i<size; i++) {
		v[i] = min+random()%diff;
	}
	return;
}

int
start_sort(int size)
{
	int *target;

	target = (int*)malloc(sizeof(int)*size);
	if (!target) {
		perror("malloc");
		exit(1);
	}

	random_initialize(target, size, 0, 1);

	//print_array(target, size);
	quicksort(target, 0, size-1);
	//selectsort(target, 0, size-1);
	//print_array(target, size);
	return check_sort(target, size);
}

int
main(int argc, char **argv)
{
	//unsigned int seed= -1074072728;
	unsigned int seed;
	int size=101;
	int loop=1;
	int opt, i;

	while ((opt = getopt(argc, argv, "t:s:n:")) != -1) {
		switch (opt) {
			case 'n':
				size = atoi(optarg);
				break;
			case 't':
				loop = atoi(optarg);
				break;
			case 's':
				seed = atoi(optarg);
				break;
			default:
				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
				exit(1);
		}
	}

	printf("start seed = %u\n", seed);
	printf("sort size = %d\n", size);
	for (i=0; i<loop; i++) {
		srandom(seed+i);
		int b = start_sort(size);
		if (b) {
			printf("seed = %d+%u, success\n", i, seed);
		} else {
			fprintf(stderr, "sorting failure!  seed=%u+%d\n", seed,i);
			exit(1);
		}
	}
	exit(0);
}