|
22
|
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
|
|
23
|
150 while ((opt = getopt(argc, argv, "t:s:n:")) != -1) {
|
|
22
|
151 switch (opt) {
|
|
23
|
152 case 'n':
|
|
22
|
153 size = atoi(optarg);
|
|
|
154 break;
|
|
23
|
155 case 't':
|
|
22
|
156 loop = atoi(optarg);
|
|
|
157 break;
|
|
23
|
158 case 's':
|
|
22
|
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
|
