Advertisement
Guest User

Untitled

a guest
Aug 20th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.43 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <limits.h>
  5. #include <string.h>
  6.  
  7. int n, i, j, p;
  8. long long OB, soma, media; //n = número de elementos que serão gerados nos vetores para serem ordenados.
  9. //OB = será usado para somar as operações básicas realizadas.
  10. clock_t tempo, t1, t2, t3, t4, t5, t6;
  11.  
  12. void troca(char *x, char *y)
  13. {
  14. char aux = *x;
  15. *x = *y;
  16. *y = aux;
  17. }
  18.  
  19. void bubbleSort(char dados[][200], int n)
  20. {
  21. int i, j;
  22. for (i = 0; i < n - 1; i++)
  23. for(j = n - 1; j > i; j--)
  24. {
  25.  
  26. OB++;
  27. if (strcmp(dados[j],dados[j-1])<0)
  28. {
  29. OB=OB+3;
  30.  
  31. troca(dados[j], dados[j - 1]);
  32. }
  33. }
  34. }
  35. void reverseSort(char dados[][200], int n)
  36. {
  37. int i, j;
  38. for (i = 0; i < n - 1; i++)
  39. for(j = n - 1; j > i; j--)
  40. {
  41.  
  42. OB++;
  43. if (strcmp(dados[j],dados[j-1])>0)
  44. {
  45. OB=OB+3;
  46.  
  47. troca(dados[j], dados[j - 1]);
  48. }
  49. }
  50. }
  51.  
  52. void shakerSort(char dados[][200], int n)
  53. {
  54. int trocou=1, i;
  55. while(trocou)
  56. {
  57. trocou = 0;
  58. for (i = (n - 1); i > 0; i--)
  59. {
  60. OB++;
  61. if(strcmp(dados[i-1],dados[i])>0)
  62. {
  63. OB=OB+3;
  64. troca(dados[i-1], dados[i]);
  65. trocou = 1;
  66. }
  67. }
  68.  
  69. for (i = 1; i < n; i++)
  70. {
  71. OB++;
  72. if(strcmp(dados[i-1],dados[i])>0)
  73. {
  74. //printf("1 %s\n", dados[i-1]);
  75. //printf("2 %s\n", dados[i]);
  76. OB=OB+3;
  77. troca(dados[i-1], dados[i]);
  78. //printf("3 %s\n", dados[i-1]);
  79. //printf("4 %s\n", dados[i]);
  80. trocou = 1;
  81. }
  82. }
  83. //printf("a");
  84. }
  85. }
  86.  
  87. void insertionSort(char dados[][200], int n)
  88. {
  89.  
  90. int i;
  91. for (i = 1; i < n; i++)
  92. {
  93. char aux[200];
  94. *aux = *dados[i];
  95. int j = 0;
  96. for (j = i; (j > 0) && (strcmp(aux,dados[j-1])<0); j--)
  97. {
  98. OB++;
  99. *dados[j] = *dados[j - 1];
  100. }
  101. *dados[j] = *aux;
  102. OB++;
  103. }
  104. }
  105.  
  106. void selectionSort(char dados[][200], int n)
  107. {
  108. int i, j;
  109. for (i = 0; i < (n - 1); i++)
  110. {
  111. // encontra o menor elemento
  112. int min = i;
  113. for (j = i + 1; j < n; j ++)
  114. {
  115. OB++;
  116. if (strcmp(dados[j],dados[min])<0)
  117. min = j;
  118. }
  119. // Troca a posição atual com o menor elemento do vetor
  120. troca(dados[min], dados[i]);
  121. OB=OB+3;
  122. }
  123. }
  124. char left[1000001][200], right[100001][200];
  125. void merge(char V[][200], int low, int mid, int high)
  126. {
  127.  
  128. int n1 = mid - low + 1;
  129. int n2 = high - mid;
  130.  
  131. int i = 0, j = 0;
  132. int x, y, k;
  133.  
  134. for (x = 0; x < n1; x++)
  135. {
  136. OB++;
  137. *left[x] = *V[low + x];
  138. }
  139. for (y = 0; y < n2; y++)
  140. {
  141. OB++;
  142. *right[y] = *V[mid + 1 + y];
  143. }
  144.  
  145. OB=OB+2;
  146.  
  147. left[n1][0] = 127;
  148. right[n2][0] = 127;
  149.  
  150. for (k = low; k <= high; k++)
  151. {
  152.  
  153. OB++;
  154. if(strcmp(left[i],right[j])<0)
  155. {
  156. OB++;
  157. *V[k] = *left[i++];
  158. }
  159. else
  160. {
  161. OB++;
  162. *V[k] = *right[j++];
  163. }
  164.  
  165. }
  166. }
  167.  
  168. void mergeSort(char V[][200], int low, int high)
  169. {
  170. if (low < high)
  171. {
  172.  
  173. int mid = (low + high) / 2;
  174. mergeSort(V, low, mid);
  175. mergeSort(V, mid + 1, high);
  176. merge(V, low, mid, high);
  177. }
  178. }
  179.  
  180. int partition(char V[][200], int low, int high)
  181. {
  182. char pivot[200];
  183. *pivot = *V[low];
  184. int i = low - 1, j = high + 1;
  185.  
  186. while (1)
  187. {
  188. do
  189. {
  190. i++;
  191. } while (V[i] < pivot);
  192.  
  193. do
  194. {
  195. j--;
  196. } while (V[j] > pivot);
  197.  
  198. if (i >= j)
  199. return j;
  200. troca(V[i], V[j]);
  201. }
  202. }
  203.  
  204. void quickSort(char V[][200], int low, int high)
  205. {
  206. if (low < high)
  207. {
  208. int pi = partition(V, low, high);
  209. quickSort(V, low, pi);
  210. quickSort(V, pi + 1, high);
  211. }
  212. }
  213. char v1[100002][200], v2[100002][200], v3[100002][200], v4[100002][200], v5[100002][200], v6[100002][200], v7[100002][200];
  214. int main ()
  215. {
  216.  
  217.  
  218. n=10000;
  219. scanf("%d", &n);
  220.  
  221. while(n<=100000)
  222. {
  223. printf("Tamanho - %d:\n", n);
  224.  
  225. soma=0;
  226.  
  227.  
  228.  
  229. srand(time(NULL));//inicio do algoritmo de geração de numeros aleatórios.
  230.  
  231. for(i=1;i<=n;i++)
  232. {
  233. p=rand()%100;
  234. p=p+1;
  235. for(j=0;j<=p;j++)
  236. {
  237. if(j!=p)
  238. v1[i][j]=97+rand()%26;
  239. else
  240. v1[i][j]='\0';
  241. }
  242. }
  243. for(i=1;i<=n;i++)
  244. {
  245. p=rand()%100;
  246. p=p+1;
  247. for(j=0;j<=p;j++)
  248. {
  249. if(j!=p)
  250. v2[i][j]=97+rand()%26;
  251. else
  252. v2[i][j]='\0';
  253. }
  254. }
  255. for(i=1;i<=n;i++)
  256. {
  257. p=rand()%100;
  258. p=p+1;
  259. for(j=0;j<=p;j++)
  260. {
  261. if(j!=p)
  262. v3[i][j]=97+rand()%26;
  263. else
  264. v3[i][j]='\0';
  265. }
  266. }
  267. for(i=1;i<=n;i++)
  268. {
  269. p=rand()%100;
  270. p=p+1;
  271. for(j=0;j<=p;j++)
  272. {
  273. if(j!=p)
  274. v4[i][j]=97+rand()%26;
  275. else
  276. v4[i][j]='\0';
  277. }
  278. }
  279. for(i=1;i<=n;i++)
  280. {
  281. p=rand()%100;
  282. p=p+1;
  283. for(j=0;j<=p;j++)
  284. {
  285. if(j!=p)
  286. v5[i][j]=97+rand()%26;
  287. else
  288. v5[i][j]='\0';
  289. }
  290. }
  291. for(i=1;i<=n;i++)
  292. {
  293. p=rand()%100;
  294. p=p+1;
  295. for(j=0;j<=p;j++)
  296. {
  297. if(j!=p)
  298. v6[i][j]=97+rand()%26;
  299. else
  300. v6[i][j]='\0';
  301. }
  302. }
  303. for(i=1;i<=n;i++)
  304. {
  305. p=rand()%100;
  306. p=p+1;
  307. for(j=0;j<=p;j++)
  308. {
  309. if(j!=p)
  310. v7[i][j]=97+rand()%26;
  311. else
  312. v7[i][j]='\0';
  313. }
  314. }
  315.  
  316. bubbleSort(v1,n+1);
  317. reverseSort(v2,n+1);
  318.  
  319.  
  320. tempo = clock();
  321. OB=0;
  322. quickSort(v1,0,n);
  323. printf("OB1 %lld\n", OB);
  324.  
  325. tempo = clock()-tempo;
  326.  
  327. t1 = clock();
  328. OB=0;
  329. quickSort(v2,0,n);
  330. printf("OB2 %lld\n", OB);
  331.  
  332. t1 = clock()-t1;
  333. t2 = clock();
  334. OB=0;
  335. quickSort(v3,0,n);
  336. printf("OB3 %lld\n", OB);
  337. soma=soma+OB;
  338. t2 = clock()-t2;
  339. t3 = clock();
  340. OB=0;
  341. quickSort(v4,0,n);
  342. printf("OB4 %lld\n", OB);
  343. soma=soma+OB;
  344. t3 = clock()-t3;
  345. t4 = clock();
  346. OB=0;
  347. quickSort(v5,0,n);
  348. printf("OB5 %lld\n", OB);
  349. soma=soma+OB;
  350. t4 = clock()-t4;
  351. t5 = clock();
  352. OB=0;
  353. quickSort(v6,0,n);
  354. printf("OB6 %lld\n", OB);
  355. soma=soma+OB;
  356. t5 = clock()-t5;
  357. t6 = clock();
  358. OB=0;
  359. quickSort(v7,0,n);
  360. printf("OB7 %lld\n", OB);
  361. soma=soma+OB;
  362. media = soma/5;
  363. printf("Media %lld\n", media);
  364. t6 = clock()-t6;
  365. printf("Tempo gasto 1 = %f segundos\n", ((float)tempo) / CLOCKS_PER_SEC);
  366. printf("Tempo gasto 2 = %f segundos\n", ((float)t1) / CLOCKS_PER_SEC);
  367. printf("Tempo gasto 3 = %f segundos\n", ((float)t2) / CLOCKS_PER_SEC);
  368. printf("Tempo gasto 4 = %f segundos\n", ((float)t3) / CLOCKS_PER_SEC);
  369. printf("Tempo gasto 5 = %f segundos\n", ((float)t4) / CLOCKS_PER_SEC);
  370. printf("Tempo gasto 6 = %f segundos\n", ((float)t5) / CLOCKS_PER_SEC);
  371. printf("Tempo gasto 7 = %f segundos\n", ((float)t6) / CLOCKS_PER_SEC);
  372.  
  373. //n=n+5000;
  374. for(i=0;i<n;i++)
  375. printf("%s\n", v2[i]);
  376. scanf("%d", &n);
  377. }
  378.  
  379. return 0;
  380. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement