API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
93
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.50 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. Rahmanovskiy Andrey
  3. 161
  4. Visual studio 2015
  5. All done
  6. */
  7. #define _CRT_SECURE_NO_WARNINGS
  8. #include<iostream>;
  9. #include<ctime>
  10. #include<Windows.h>
  11. #include<time.h>
  12. #include<algorithm>
  13. #include<string>
  14. #include<cstring>
  15. using namespace std;
  16.  
  17. const int count1 = 100;
  18. const int maxm = 8000;
  19. const int sorts_cnt = 7;
  20. const int MAXN = 9000;
  21. const int MINN = 1000;
  22.  
  23. union union1 { // union
  24. unsigned int a;
  25. unsigned char b[4];
  26. };
  27.  
  28. void radix_sort(int Array[], int N) {
  29. union1* my_un = new union1[N];
  30. int* values_cnt;
  31. union1* Helper;
  32. for (int i = 0; i < N; i++)
  33. my_un[i].a = Array[i];
  34. for (int byt = 0; byt < 4; byt++) // Share the bytes
  35. {
  36. int max1 = 256;
  37. values_cnt = new int[max1];
  38. Helper = new union1[N];
  39. for (int i = 0; i < max1; i++) // Count sort
  40. values_cnt[i] = 0;
  41. for (int i = 0; i < N; i++)
  42. values_cnt[my_un[i].b[byt]]++;
  43. for (int i = 1; i < max1; i++)
  44. values_cnt[i] = values_cnt[i] + values_cnt[i - 1];
  45. for (int i = N - 1; i >= 0; --i)
  46. {
  47. Helper[values_cnt[my_un[i].b[byt]] - 1] = my_un[i];
  48. values_cnt[my_un[i].b[byt]] = values_cnt[my_un[i].b[byt]] - 1;
  49. }
  50. for (int i = 0; i < N; i++)
  51. my_un[i] = Helper[i];
  52. }
  53. for (int i = 0; i < N; i++)
  54. Array[i] = my_un[i].a;
  55.  
  56. }
  57.  
  58. void count_sort(int Array_copy[], int N) {
  59. int *values_cnt = new int[maxm];
  60. int *Helper = new int[N];
  61. for (int i = 0; i < maxm; i++)
  62. values_cnt[i] = 0;
  63. for (int i = 0; i < N; i++)
  64. values_cnt[Array_copy[i]]++;
  65. for (int j = 1; j < maxm; j++)
  66. values_cnt[j] = values_cnt[j] + values_cnt[j - 1];
  67. for (int i = N - 1; i >= 0; i--) {
  68. Helper[values_cnt[Array_copy[i]] - 1] = Array_copy[i];
  69. values_cnt[Array_copy[i]] = values_cnt[Array_copy[i]] - 1;
  70. }
  71. for (int i = 0; i < N; i++)
  72. Array_copy[i] = Helper[i];
  73. }
  74.  
  75. void insertion_sort(int Array[], int N) {
  76. for (int i = 1; i < N; i++) {
  77. for (int j = i - 1; j >= 0; j--) {
  78. if (Array[j] > Array[j + 1]) {
  79. int t = Array[j];
  80. Array[j] = Array[j + 1];
  81. Array[j + 1] = t;
  82. }
  83. }
  84. }
  85. }
  86.  
  87.  
  88. void binary_insertion_sort(int Array[], int N) {
  89. for (int i = 1; i < N; i++) {
  90. int pos = 0, r = i;
  91. while (r - pos != 0) {
  92. int c = (r + pos) / 2;
  93. if (Array[c] > Array[i])
  94. r = c;
  95. else
  96. pos = c + 1;
  97. }
  98. int tmp = Array[i]; // Save current element
  99. for (int j = i; j > pos; j--) // shift to the right
  100. {
  101. Array[j] = Array[j - 1];
  102. }
  103. Array[pos] = tmp;
  104. }
  105. }
  106. void bubble(int Array[], int N) {
  107. for (int i = 0; i < N; i++) {
  108. for (int j = 0; j < N - i - 1; j++) {
  109. if (Array[j] > Array[j + 1]) {
  110. int t = Array[j];
  111. Array[j] = Array[j + 1];
  112. Array[j + 1] = t;
  113. }
  114. }
  115. }
  116. }
  117.  
  118. void bubble_Aiverson1(int Array[], int N) { // Пузырек с 1 условием Айверсона
  119. for (int i = 0; i < N; i++) {
  120. bool count_change = 0;
  121. for (int j = 0; j < N - i - 1; j++) {
  122. if (Array[j] > Array[j + 1]) {
  123. int t = Array[j];
  124. Array[j] = Array[j + 1];
  125. Array[j + 1] = t;
  126. count_change = 1; // Check changes
  127. }
  128. }
  129. if (!count_change) // if not changes - break
  130. return;
  131. }
  132. }
  133. void bubble_Aiverson2(int Array[], int N) {
  134. int last_change = N - 1;
  135. int last_change_now = N - 1;
  136. for (int i = 0; i < N; i++) {
  137. if (last_change_now == 0)
  138. return;
  139. last_change = last_change_now;
  140. last_change_now = 0;
  141. for (int j = 0; j < last_change; j++) {
  142. if (Array[j] > Array[j + 1]) {
  143. int t = Array[j];
  144. Array[j] = Array[j + 1];
  145. Array[j + 1] = t;
  146. last_change_now = j;
  147. }
  148. }
  149. }
  150. }
  151.  
  152. void Clean(int Array_copy[], int Array[], int N) { // Clean changable array
  153. for (int i = 0; i < N; i++) // copy array
  154. Array_copy[i] = Array[i];
  155. }
  156.  
  157. typedef void(*pf)(int Array[], int N); // A pointer to the function
  158. int main() {
  159. DWORD each_sort_info[7][4][9];
  160. freopen("out.csv", "w", stdout);
  161. setlocale(LC_ALL, "Russian"); // Russian language
  162. srand(time(0)); // Random
  163. cout << endl;
  164. pair<string, pf> *Array_sorts = new pair<string, pf>[sorts_cnt];
  165.  
  166. Array_sorts[0].first = "Bubble";
  167. Array_sorts[0].second = bubble;
  168.  
  169. Array_sorts[1].first = "Bubble with Aiverson 1";
  170. Array_sorts[1].second = bubble_Aiverson1;
  171.  
  172. Array_sorts[2].first = "Bubble with Aiverson 2";
  173. Array_sorts[2].second = bubble_Aiverson2;
  174.  
  175. Array_sorts[3].first = "Insertion sort";
  176. Array_sorts[3].second = insertion_sort;
  177.  
  178. Array_sorts[4].first = "Binary insertion sort";
  179. Array_sorts[4].second = binary_insertion_sort;
  180.  
  181. Array_sorts[5].first = "Count sort";
  182. Array_sorts[5].second = count_sort;
  183.  
  184. Array_sorts[6].first = "Radix sort";
  185. Array_sorts[6].second = radix_sort;
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194. cout << "Lenght of Array;";
  195. for (int i = 0; i < sorts_cnt; i++)
  196. cout << Array_sorts[i].first << ";";
  197. int *Global_array = new int[MAXN]; // Create main array
  198. for (int i = 0; i < MAXN; i++)
  199. Global_array[i] = rand() % 8;
  200. for (int N = MINN; N <= MAXN; N += MINN) { // 1000, 2000 ... 9000
  201. cout << endl;
  202. cout << N << ";";
  203. int *Array = new int[N];
  204. for (int i = 0; i < N; i++) // Create immutable internal array
  205. Array[i] = Global_array[i];
  206.  
  207. int *Array_copy = new int[N];
  208. for (int i = 0; i < sorts_cnt; i++) {
  209. Clean(Array_copy, Array, N);
  210. Array_sorts[i].second(Array_copy, N); // Optimizing compiler
  211. }
  212.  
  213. for (int sort_num = 0; sort_num < sorts_cnt; sort_num++) { // Enumeration sorts
  214. LARGE_INTEGER sred;
  215. sred.QuadPart = 0;
  216. //cout << Array_sorts[sort_num].first << endl;
  217. Clean(Array_copy, Array, N);
  218. for (int i = 0; i < count1; i++) { // Statr sotring 100 count
  219. Clean(Array_copy, Array, N);
  220. LARGE_INTEGER Fr, StT, FT, TT;
  221. QueryPerformanceFrequency(&Fr); // Count time
  222. QueryPerformanceCounter(&StT);
  223.  
  224. Array_sorts[sort_num].second(Array_copy, N); // statr sorting
  225.  
  226. QueryPerformanceCounter(&FT);
  227. TT.QuadPart = (FT.QuadPart - StT.QuadPart);
  228. TT.QuadPart = TT.QuadPart * 1000000000 / Fr.QuadPart;
  229. sred.QuadPart += TT.QuadPart;
  230. }
  231. cout << sred.QuadPart / count1<< ";";
  232. each_sort_info[sort_num][0][N / MINN - 1] = sred.QuadPart / count1; // Save dates
  233. //print(Array_copy, N);
  234. }
  235. delete[] Array_copy; // Очистка памяти
  236. delete[] Array;
  237. }
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248. freopen("out2.csv", "w", stdout);
  249. cout << "Lenght of Array;";
  250. for (int i = 0; i < sorts_cnt; i++)
  251. if (i != 5)
  252. cout << Array_sorts[i].first << ";";
  253. for (int i = 0; i < MAXN; i++)
  254. Global_array[i] = rand();
  255. for (int N = MINN; N <= MAXN; N += MINN) {
  256. cout << endl;
  257. cout << N << ";";
  258. int *Array = new int[N];
  259. for (int i = 0; i < N; i++)
  260. Array[i] = Global_array[i];
  261. int *Array_copy = new int[N];
  262. for (int i = 0; i < sorts_cnt; i++) {
  263. if (i == 5)
  264. continue;
  265. Clean(Array_copy, Array, N);
  266. Array_sorts[i].second(Array_copy, N);
  267. }
  268. for (int sort_num = 0; sort_num < sorts_cnt; sort_num++) {
  269. if (sort_num == 5)
  270. continue;
  271. LARGE_INTEGER sred;
  272. sred.QuadPart = 0;
  273. Clean(Array_copy, Array, N);
  274. for (int i = 0; i < count1; i++) {
  275. Clean(Array_copy, Array, N);
  276. LARGE_INTEGER Fr, StT, FT, TT;
  277. QueryPerformanceFrequency(&Fr);
  278. QueryPerformanceCounter(&StT);
  279.  
  280. Array_sorts[sort_num].second(Array_copy, N);
  281.  
  282. QueryPerformanceCounter(&FT);
  283. TT.QuadPart = (FT.QuadPart - StT.QuadPart);
  284. TT.QuadPart = TT.QuadPart * 1000000000 / Fr.QuadPart;
  285. sred.QuadPart += TT.QuadPart;
  286. }
  287. cout << sred.QuadPart / count1 << ";";
  288. each_sort_info[sort_num][1][N / MINN - 1] = sred.QuadPart / count1;
  289. }
  290. delete[] Array_copy; // Clean memory
  291. delete[] Array;
  292. }
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303. freopen("out3.csv", "w", stdout);
  304. cout << "Lenght of Array;";
  305. for (int i = 0; i < sorts_cnt; i++)
  306. cout << Array_sorts[i].first << ";";
  307. for (int i = 0; i < MAXN; i++)
  308. Global_array[i] = rand() % maxm;
  309. bubble(Global_array, MAXN);
  310. for (int N = MINN; N <= MAXN; N += MINN) {
  311. cout << endl;
  312. cout << N << ";";
  313. int *Array = new int[N];
  314. for (int i = 0; i < N; i++)
  315. Array[i] = Global_array[i];
  316. for (int i = 0; i < 5; i++) {
  317. int x = rand() % N;
  318. int y = rand() % N;
  319. swap(Array[x], Array[y]);
  320. }
  321.  
  322. int *Array_copy = new int[N];
  323. for (int i = 0; i < sorts_cnt; i++) {
  324. Clean(Array_copy, Array, N);
  325. Array_sorts[i].second(Array_copy, N);
  326. }
  327.  
  328. for (int sort_num = 0; sort_num < sorts_cnt; sort_num++) {
  329. LARGE_INTEGER sred;
  330. sred.QuadPart = 0;
  331. Clean(Array_copy, Array, N);
  332. for (int i = 0; i < count1; i++) {
  333. Clean(Array_copy, Array, N);
  334. LARGE_INTEGER Fr, StT, FT, TT;
  335. QueryPerformanceFrequency(&Fr);
  336. QueryPerformanceCounter(&StT);
  337.  
  338. Array_sorts[sort_num].second(Array_copy, N);
  339.  
  340. QueryPerformanceCounter(&FT);
  341. TT.QuadPart = (FT.QuadPart - StT.QuadPart);
  342. TT.QuadPart = TT.QuadPart * 1000000000 / Fr.QuadPart;
  343. sred.QuadPart += TT.QuadPart;
  344. }
  345. cout << sred.QuadPart / count1 << ";";
  346. each_sort_info[sort_num][2][N / MINN - 1] = sred.QuadPart / count1;
  347. }
  348. delete[] Array_copy; // Clean memmory
  349. delete[] Array;
  350. }
  351.  
  352.  
  353.  
  354.  
  355.  
  356. freopen("out4.csv", "w", stdout);
  357. cout << "Lenght of Array;";
  358. for (int i = 0; i < sorts_cnt; i++)
  359. cout << Array_sorts[i].first << ";";
  360. for (int i = 0; i < MAXN; i++)
  361. Global_array[i] = rand() % maxm;
  362. bubble(Global_array, MAXN);
  363. int *Global_array1 = new int[MAXN];
  364. for (int i = 0; i < MAXN; i++)
  365. Global_array1[i] = Global_array[MAXN - i - 1];
  366. for (int i = 0; i < MAXN; i++)
  367. Global_array[i] = Global_array1[i];
  368. for (int N = MINN; N <= MAXN; N += MINN) {
  369. cout << endl;
  370. cout << N << ";";
  371. int *Array = new int[N];
  372. for (int i = 0; i < N; i++)
  373. Array[i] = Global_array[i];
  374. for (int i = 0; i < 5; i++) {
  375. int x = rand() % N;
  376. int y = rand() % N;
  377. swap(Array[x], Array[y]);
  378. }
  379.  
  380. int *Array_copy = new int[N];
  381. for (int i = 0; i < sorts_cnt; i++) {
  382. Clean(Array_copy, Array, N);
  383. Array_sorts[i].second(Array_copy, N);
  384. }
  385.  
  386. for (int sort_num = 0; sort_num < sorts_cnt; sort_num++) {
  387. LARGE_INTEGER sred;
  388. sred.QuadPart = 0;
  389. Clean(Array_copy, Array, N);
  390. for (int i = 0; i < count1; i++) {
  391. Clean(Array_copy, Array, N);
  392. LARGE_INTEGER Fr, StT, FT, TT;
  393. QueryPerformanceFrequency(&Fr);
  394. QueryPerformanceCounter(&StT);
  395.  
  396. Array_sorts[sort_num].second(Array_copy, N);
  397.  
  398. QueryPerformanceCounter(&FT);
  399. TT.QuadPart = (FT.QuadPart - StT.QuadPart);
  400. TT.QuadPart = TT.QuadPart * 1000000000 / Fr.QuadPart;
  401. sred.QuadPart += TT.QuadPart;
  402. }
  403. cout << sred.QuadPart / count1 << ";";
  404. each_sort_info[sort_num][3][N / MINN - 1] = sred.QuadPart / count1;
  405. }
  406. delete[] Array_copy; // Clean memory
  407. delete[] Array;
  408. }
  409.  
  410. // Write date about each sort
  411. freopen("1.csv", "w", stdout);
  412. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  413. for (int j = 0; j < 9; j++) {
  414. cout << (j + 1) * MINN << ";";
  415. for (int k = 0; k < 4; k++) {
  416. cout << each_sort_info[0][k][j] << ";";
  417. }
  418. cout << endl;
  419. }
  420.  
  421. freopen("2.csv", "w", stdout);
  422. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  423. for (int j = 0; j < 9; j++) {
  424. cout << (j + 1) * MINN << ";";
  425. for (int k = 0; k < 4; k++) {
  426. cout << each_sort_info[1][k][j] << ";";
  427. }
  428. cout << endl;
  429. }
  430.  
  431. freopen("3.csv", "w", stdout);
  432. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  433. for (int j = 0; j < 9; j++) {
  434. cout << (j + 1) * MINN << ";";
  435. for (int k = 0; k < 4; k++) {
  436. cout << each_sort_info[2][k][j] << ";";
  437. }
  438. cout << endl;
  439. }
  440.  
  441.  
  442. freopen("4.csv", "w", stdout);
  443. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  444. for (int j = 0; j < 9; j++) {
  445. cout << (j + 1) * MINN << ";";
  446. for (int k = 0; k < 4; k++) {
  447. cout << each_sort_info[3][k][j] << ";";
  448. }
  449. cout << endl;
  450. }
  451.  
  452.  
  453. freopen("5.csv", "w", stdout);
  454. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  455. for (int j = 0; j < 9; j++) {
  456. cout << (j + 1) * MINN << ";";
  457. for (int k = 0; k < 4; k++) {
  458. cout << each_sort_info[4][k][j] << ";";
  459. }
  460. cout << endl;
  461. }
  462.  
  463.  
  464. freopen("6.csv", "w", stdout);
  465. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  466. for (int j = 0; j < 9; j++) {
  467. cout << (j + 1) * MINN << ";";
  468. for (int k = 0; k < 4; k++) {
  469. cout << each_sort_info[5][k][j] << ";";
  470. }
  471. cout << endl;
  472. }
  473.  
  474.  
  475. freopen("7.csv", "w", stdout);
  476. cout << "Lenght of array; 0-7; max int; near sort; revers;" << endl;
  477. for (int j = 0; j < 9; j++) {
  478. cout << (j + 1) * MINN << ";";
  479. for (int k = 0; k < 4; k++) {
  480. cout << each_sort_info[6][k][j] << ";";
  481. }
  482. cout << endl;
  483. }
  484.  
  485. delete[] Global_array;
  486. delete[] Global_array1;
  487. //system("pause");
  488. return 0;
  489. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!