#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double urandom() { /***  0 以上1より小さい値を返す  ***/
    return rand() / (1.0 + RAND_MAX);
}

int nrandom(int n) { /*** 0からn-1までを返す  ***/
	return (int) (n * urandom()); /***  rand()%n だと性質が悪い  ***/
}

int *make_data(unsigned int seed, int n) {
	int i, *mem;

	srand(seed);
	mem = malloc(n * sizeof(int));
	if (mem == NULL) {
		printf("malloc error!\n");
		exit(1);
	}
	for (i = 0; i < n; i++) {
		mem[i] = nrandom(n);
	}
	return mem;
}

void print_vec(int a[], int size) {
	int i;
	for (i = 0; i < size; i++) {
		printf("%d ", a[i]);
	}
	putchar('\n');
}

/* 問題１ */
void partition(int a[], int n, int x) {
	int i;
	int l = 0;
	int r = n - 1;
	int t;
	while (l < r) {
		while (a[l] <= x) {
			l++;
		}
		while (x < a[r]) {
			r--;
		}
		if (r < l) {
			break;
		}
		t = a[l];
		a[l] = a[r];
		a[r] = t;
		l++;
		r--;
	}
	printf("pivot:%d\n", x);
	printf("left:");
	for (i = 0; i < l; i++) {
		printf("%d, ", a[i]);
	}
	printf("\n");
	printf("right:");
	for (i = l; i < n; i++) {
		printf("%d, ", a[i]);
	}
	printf("\n");
}

/* 問題２ */
void quick(int a[], int low, int upp) {
	int x;
	int l;
	int r;
	int t;
	
	if (upp <= low) {
		return;
	}
	l = low;
	r = upp;
	x = a[low];
	while (l <= r) {
		while (a[l] < x) {
			l++;
		}
		while (x < a[r]) {
			r--;
		}
		if (r < l) {
			break;
		}
		t = a[l];
		a[l] = a[r];
		a[r] = t;
		l++;
		r--;
	}
	quick(a, low, r);
	quick(a, l, upp);
}

/* 問題３ */
void quick2(int a[], int low, int upp) {
	int x;
	int l;
	int r;
	int t;
	int mid;
	
	if (upp <= low) {
		return;
	}
	l = low;
	r = upp;
	mid = ((upp - low) >> 1) + low;
	if (a[low] < a[mid]) {
		if (a[mid] < a[upp]) {
			x = a[mid];
		} else if (a[low] < a[upp]) {
			x = a[upp];
		} else {
			x = a[low];
		}
	} else {
		if (a[low] < a[upp]) {
			x = a[low];
		} else if (a[mid] < a[upp]) {
			x = a[upp];
		} else {
			x = a[low];
		}
	}
	while (l <= r) {
		while (a[l] < x) {
			l++;
		}
		while (x < a[r]) {
			r--;
		}
		if (r < l) {
			break;
		}
		t = a[l];
		a[l] = a[r];
		a[r] = t;
		l++;
		r--;
	}
	quick2(a, low, r);
	quick2(a, l, upp);
}

void insertionsort(int a[], int low, int upp) {
	int i;
	int j;
	int t;
	for (i = low + 1; i <= upp; i++) {
		t = a[i];
		for (j = i; low < j; j--) {
			if (a[j - 1] <= t) {
				break;
			}
			a[j] = a[j - 1];
		}
		a[j] = t;
	}
}

/* 問題４ */
void quick3(int a[], int low, int upp) {
	int x;
	int l;
	int r;
	int t;
	int mid;
	
	if (upp - low < 10) {
		insertionsort(a, low, upp);
		return;
	}
	l = low;
	r = upp;
	mid = ((upp - low) >> 1) + low;
	if (a[low] < a[mid]) {
		if (a[mid] < a[upp]) {
			x = a[mid];
		} else if (a[low] < a[upp]) {
			x = a[upp];
		} else {
			x = a[low];
		}
	} else {
		if (a[low] < a[upp]) {
			x = a[low];
		} else if (a[mid] < a[upp]) {
			x = a[upp];
		} else {
			x = a[low];
		}
	}
	while (l <= r) {
		while (a[l] < x) {
			l++;
		}
		while (x < a[r]) {
			r--;
		}
		if (r < l) {
			break;
		}
		t = a[l];
		a[l] = a[r];
		a[r] = t;
		l++;
		r--;
	}
	quick3(a, low, r);
	quick3(a, l, upp);
}

/* 問題５ */
int main() {
	int *a, s, n;
	int i;
	int *b;
	time_t start;
	time_t end;
	
	printf("seed? ");
	scanf("%d", &s);
	printf("n? ");
	scanf("%d", &n);
	a = make_data(s, n);
	
	b = malloc(sizeof(int) * n);
	for (i = 0; i < n; i++) {
		b[i] = a[i];
	}
	start = clock();
	quick(b, 0, n - 1);
	end = clock();
	free(b);
	printf("quick : %f\n", (double)end - start);
	
	b = malloc(sizeof(int) * n);
	for (i = 0; i < n; i++) {
		b[i] = a[i];
	}
	start = clock();
	quick2(b, 0, n - 1);
	end = clock();
	free(b);
	printf("quick2 : %f\n", (double)end - start);

	b = malloc(sizeof(int) * n);
	for (i = 0; i < n; i++) {
		b[i] = a[i];
	}
	start = clock();
	quick3(b, 0, n - 1);
	end = clock();
	free(b);
	printf("quick3 : %f\n", (double)end - start);

	return 0;
}