--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CbC-examples/quicksort/quicksort_c.c	Tue Oct 13 17:15:58 2009 +0900
@@ -0,0 +1,183 @@
+#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, "r:s:n:")) != -1) {
+		switch (opt) {
+			case 's':
+				size = atoi(optarg);
+				break;
+			case 'n':
+				loop = atoi(optarg);
+				break;
+			case 'r':
+				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);
+}
+
+
+