fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. double urandom() { /***  0 以上1より小さい値を返す  ***/
  5.     return rand() / (1.0 + RAND_MAX);
  6. }
  7.  
  8. int nrandom(int n) { /*** 0からn-1までを返す  ***/
  9. 	return (int) (n * urandom()); /***  rand()%n だと性質が悪い  ***/
  10. }
  11.  
  12. int *make_data(unsigned int seed, int n) {
  13. 	int i, *mem;
  14.  
  15. 	srand(seed);
  16. 	mem = malloc(n * sizeof(int));
  17. 	if (mem == NULL) {
  18. 		printf("malloc error!\n");
  19. 		exit(1);
  20. 	}
  21. 	for (i = 0; i < n; i++) {
  22. 		mem[i] = nrandom(n);
  23. 	}
  24. 	return mem;
  25. }
  26.  
  27. void print_vec(int a[], int size) {
  28. 	int i;
  29. 	for (i = 0; i < size; i++) {
  30. 		printf("%d ", a[i]);
  31. 	}
  32. 	putchar('\n');
  33. }
  34.  
  35. /* 問題１ */
  36. void partition(int a[], int n, int x) {
  37. 	int i;
  38. 	int l = 0;
  39. 	int r = n - 1;
  40. 	int t;
  41. 	while (l < r) {
  42. 		while (a[l] <= x) {
  43. 			l++;
  44. 		}
  45. 		while (x < a[r]) {
  46. 			r--;
  47. 		}
  48. 		if (r < l) {
  49. 			break;
  50. 		}
  51. 		t = a[l];
  52. 		a[l] = a[r];
  53. 		a[r] = t;
  54. 		l++;
  55. 		r--;
  56. 	}
  57. 	printf("pivot:%d\n", x);
  58. 	printf("left:");
  59. 	for (i = 0; i < l; i++) {
  60. 		printf("%d, ", a[i]);
  61. 	}
  62. 	printf("\n");
  63. 	printf("right:");
  64. 	for (i = l; i < n; i++) {
  65. 		printf("%d, ", a[i]);
  66. 	}
  67. 	printf("\n");
  68. }
  69.  
  70. /* 問題２ */
  71. void quick(int a[], int low, int upp) {
  72. 	int x;
  73. 	int l;
  74. 	int r;
  75. 	int t;
  76.  
  77. 	if (upp <= low) {
  78. 		return;
  79. 	}
  80. 	l = low;
  81. 	r = upp;
  82. 	x = a[low];
  83. 	while (l <= r) {
  84. 		while (a[l] < x) {
  85. 			l++;
  86. 		}
  87. 		while (x < a[r]) {
  88. 			r--;
  89. 		}
  90. 		if (r < l) {
  91. 			break;
  92. 		}
  93. 		t = a[l];
  94. 		a[l] = a[r];
  95. 		a[r] = t;
  96. 		l++;
  97. 		r--;
  98. 	}
  99. 	quick(a, low, r);
  100. 	quick(a, l, upp);
  101. }
  102.  
  103. /* 問題３ */
  104. void quick2(int a[], int low, int upp) {
  105. 	int x;
  106. 	int l;
  107. 	int r;
  108. 	int t;
  109. 	int mid;
  110.  
  111. 	if (upp <= low) {
  112. 		return;
  113. 	}
  114. 	l = low;
  115. 	r = upp;
  116. 	mid = ((upp - low) >> 1) + low;
  117. 	if (a[low] < a[mid]) {
  118. 		if (a[mid] < a[upp]) {
  119. 			x = a[mid];
  120. 		} else if (a[low] < a[upp]) {
  121. 			x = a[upp];
  122. 		} else {
  123. 			x = a[low];
  124. 		}
  125. 	} else {
  126. 		if (a[low] < a[upp]) {
  127. 			x = a[low];
  128. 		} else if (a[mid] < a[upp]) {
  129. 			x = a[upp];
  130. 		} else {
  131. 			x = a[low];
  132. 		}
  133. 	}
  134. 	while (l <= r) {
  135. 		while (a[l] < x) {
  136. 			l++;
  137. 		}
  138. 		while (x < a[r]) {
  139. 			r--;
  140. 		}
  141. 		if (r < l) {
  142. 			break;
  143. 		}
  144. 		t = a[l];
  145. 		a[l] = a[r];
  146. 		a[r] = t;
  147. 		l++;
  148. 		r--;
  149. 	}
  150. 	quick2(a, low, r);
  151. 	quick2(a, l, upp);
  152. }
  153.  
  154. void insertionsort(int a[], int low, int upp) {
  155. 	int i;
  156. 	int j;
  157. 	int t;
  158. 	for (i = low + 1; i <= upp; i++) {
  159. 		t = a[i];
  160. 		for (j = i; low < j; j--) {
  161. 			if (a[j - 1] <= t) {
  162. 				break;
  163. 			}
  164. 			a[j] = a[j - 1];
  165. 		}
  166. 		a[j] = t;
  167. 	}
  168. }
  169.  
  170. /* 問題４ */
  171. void quick3(int a[], int low, int upp) {
  172. 	int x;
  173. 	int l;
  174. 	int r;
  175. 	int t;
  176. 	int mid;
  177.  
  178. 	if (upp - low < 10) {
  179. 		insertionsort(a, low, upp);
  180. 		return;
  181. 	}
  182. 	l = low;
  183. 	r = upp;
  184. 	mid = ((upp - low) >> 1) + low;
  185. 	if (a[low] < a[mid]) {
  186. 		if (a[mid] < a[upp]) {
  187. 			x = a[mid];
  188. 		} else if (a[low] < a[upp]) {
  189. 			x = a[upp];
  190. 		} else {
  191. 			x = a[low];
  192. 		}
  193. 	} else {
  194. 		if (a[low] < a[upp]) {
  195. 			x = a[low];
  196. 		} else if (a[mid] < a[upp]) {
  197. 			x = a[upp];
  198. 		} else {
  199. 			x = a[low];
  200. 		}
  201. 	}
  202. 	while (l <= r) {
  203. 		while (a[l] < x) {
  204. 			l++;
  205. 		}
  206. 		while (x < a[r]) {
  207. 			r--;
  208. 		}
  209. 		if (r < l) {
  210. 			break;
  211. 		}
  212. 		t = a[l];
  213. 		a[l] = a[r];
  214. 		a[r] = t;
  215. 		l++;
  216. 		r--;
  217. 	}
  218. 	quick3(a, low, r);
  219. 	quick3(a, l, upp);
  220. }
  221.  
  222. /* 問題５ */
  223. int main() {
  224. 	int *a, s, n;
  225. 	int i;
  226. 	int *b;
  227. 	time_t start;
  228. 	time_t end;
  229.  
  230. 	printf("seed? ");
  231. 	scanf("%d", &s);
  232. 	printf("n? ");
  233. 	scanf("%d", &n);
  234. 	a = make_data(s, n);
  235.  
  236. 	b = malloc(sizeof(int) * n);
  237. 	for (i = 0; i < n; i++) {
  238. 		b[i] = a[i];
  239. 	}
  240. 	start = clock();
  241. 	quick(b, 0, n - 1);
  242. 	end = clock();
  243. 	free(b);
  244. 	printf("quick : %f\n", (double)end - start);
  245.  
  246. 	b = malloc(sizeof(int) * n);
  247. 	for (i = 0; i < n; i++) {
  248. 		b[i] = a[i];
  249. 	}
  250. 	start = clock();
  251. 	quick2(b, 0, n - 1);
  252. 	end = clock();
  253. 	free(b);
  254. 	printf("quick2 : %f\n", (double)end - start);
  255.  
  256. 	b = malloc(sizeof(int) * n);
  257. 	for (i = 0; i < n; i++) {
  258. 		b[i] = a[i];
  259. 	}
  260. 	start = clock();
  261. 	quick3(b, 0, n - 1);
  262. 	end = clock();
  263. 	free(b);
  264. 	printf("quick3 : %f\n", (double)end - start);
  265.  
  266. 	return 0;
  267. }
Success #stdin #stdout 0.06s 2596KB
comments (?)
stdin
copy 
666
100000
stdout
copy 
seed? n? quick : 10000.000000
quick2 : 10000.000000
quick3 : 20000.000000
https://ideone.com/HaUD18
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!