Mercurial > hg > CbC > CbC_gcc

comparison CbC-examples/quicksort/quicksort_c.c @ 22:0eb6cac880f0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add cbc example of quicksort.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 13 Oct 2009 17:15:58 +0900
parents
children 775dfe898662
comparison
equal deleted inserted replaced
21:959d4c8c8abc 22:0eb6cac880f0
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<unistd.h>
4 #include<assert.h>
5
6 static inline void
7 SWAP (int *a, int *b)
8 {
9 int tmp;
10 tmp = *a;
11 *a = *b;
12 *b = tmp;
13 }
14
15 static inline int
16 mid_point(int a, int b, int c)
17 {
18 if (a < b) {
19 if (b < c)
20 return b;
21 else if (a < c)
22 return c;
23 else
24 return a;
25 } else {
26 if (a < c)
27 return a;
28 else if (b < c)
29 return c;
30 else
31 return b;
32 }
33 }
34
35 void
36 selectsort(int *v, int s0, int e0)
37 {
38 int i,j;
39 int m;
40 int size = e0-s0+1;
41 v += s0;
42 for (i=0; i<size; i++) {
43 m = i;
44 for (j=i+1; j<size; j++) {
45 if (v[m] > v[j])
46 m = j;
47 }
48 if (m!=i)
49 SWAP(&v[i],&v[m]);
50 }
51 return;
52 }
53
54 void
55 quicksort(int *v, int s0, int e0)
56 {
57 int p;
58 int s=s0, e=e0;
59 #if 0
60 if (e<=s) return;
61 if (e-s<5) {
62 selectsort(v,s0,e0);
63 return;
64 }
65 #else
66 if (e<=s) return;
67 #endif
68
69 //p = (v[s]+v[(s+e)/2]+v[e])/3;
70 p = mid_point(v[s],v[e],v[(s+e)/2]);
71
72 while (1) {
73 while (v[s]<p) s++;
74 while (p<v[e]) e--;
75
76 if (!(s<e)) break;
77 SWAP(&v[s], &v[e]);
78 s++; e--;
79 }
80 assert(e+1==s || s==e);
81
82 quicksort(v, s0, e);
83 quicksort(v, e+1, e0);
84 return;
85 }
86
87 static void
88 print_array(int *v, int size)
89 {
90 int i;
91 printf("[");
92 for (i=0; i<size; i++) {
93 printf("%s%4d", (i%10==0)? "\n ":" ", v[i]);
94 }
95 printf("]\n");
96 }
97
98 static int
99 check_sort(int *v, int size)
100 {
101 int i;
102 for (i=0; i<size-1; i++) {
103 if (v[i] > v[i+1])
104 return 0;
105 }
106 return 1;
107 }
108
109 void
110 random_initialize(int *v, int size, int min, int max)
111 {
112 int i;
113 int diff = max-min+1;
114
115 for (i=0; i<size; i++) {
116 v[i] = min+random()%diff;
117 }
118 return;
119 }
120
121 int
122 start_sort(int size)
123 {
124 int *target;
125
126 target = (int*)malloc(sizeof(int)*size);
127 if (!target) {
128 perror("malloc");
129 exit(1);
130 }
131
132 random_initialize(target, size, 0, 1);
133
134 //print_array(target, size);
135 quicksort(target, 0, size-1);
136 //selectsort(target, 0, size-1);
137 //print_array(target, size);
138 return check_sort(target, size);
139 }
140
141 int
142 main(int argc, char **argv)
143 {
144 //unsigned int seed= -1074072728;
145 unsigned int seed;
146 int size=101;
147 int loop=1;
148 int opt, i;
149
150 while ((opt = getopt(argc, argv, "r:s:n:")) != -1) {
151 switch (opt) {
152 case 's':
153 size = atoi(optarg);
154 break;
155 case 'n':
156 loop = atoi(optarg);
157 break;
158 case 'r':
159 seed = atoi(optarg);
160 break;
161 default:
162 fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
163 exit(1);
164 }
165 }
166
167 printf("start seed = %u\n", seed);
168 printf("sort size = %d\n", size);
169 for (i=0; i<loop; i++) {
170 srandom(seed+i);
171 int b = start_sort(size);
172 if (b) {
173 printf("seed = %d+%u, success\n", i, seed);
174 } else {
175 fprintf(stderr, "sorting failure! seed=%u+%d\n", seed,i);
176 exit(1);
177 }
178 }
179 exit(0);
180 }
181
182
183