### view CbC-examples/quicksort/quicksort_c.c @ 23:775dfe898662

author kent Wed, 14 Oct 2009 12:12:51 +0900 0eb6cac880f0
line wrap: on
line source
```
#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);
}

```