Advertisement
Guest User

Untitled

a guest
May 23rd, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.81 KB | None | 0 0
  1. // Lab_darbas3_v2.cpp. Trecias laboratorinis darbas: rusiavimo algoritmai.
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include <iostream>
  6. #include <algorithm> // atsitiktinai sumaisytu aibiu generavimui su random_shuffle
  7. #include <vector>
  8. #include <ctime>
  9. using namespace std;
  10.  
  11. int Pvs, Kvs; // Pvs - palyginimu veiksmu skaicius, Kvs - kopijavimu veiksmu skaicius
  12.  
  13. // Iterpimo algorimas (Insertion sort)
  14. void IterpimoAlgoritmas(vector<int>&masyvas) {
  15.  
  16. for (int i = 1; i < (int)masyvas.size(); i++) {
  17. int v = masyvas[i];
  18. int j = i;
  19. Kvs++;
  20.  
  21. for (int i = 1; i < (int)masyvas.size(); i++)
  22. {
  23. if (masyvas[j - 1] > v)
  24. {
  25. Pvs++;
  26. masyvas[j] = masyvas[j - 1];
  27. Kvs++;
  28. j = j - 1;
  29. if (j == 0) // iseiname is ciklo
  30. break;
  31. }
  32. else
  33. {
  34. Pvs++;
  35. break;
  36. }
  37. }
  38. masyvas[j] = v;
  39. }
  40. }
  41.  
  42. int partition(vector<int> &masyvas, int start, int end)
  43. {
  44. int pivot = masyvas[end];
  45. int pind = start;
  46. int t;
  47. for (int i = start; i<end; i++)
  48. {
  49. if (masyvas[i] <= pivot)
  50. {
  51. Pvs++;
  52.  
  53. //swap
  54. t = masyvas[i];
  55. masyvas[i] = masyvas[pind];
  56. masyvas[pind] = t;
  57.  
  58. pind++;
  59. Kvs = Kvs + 3;
  60. }
  61. else
  62. Pvs++;
  63. }
  64.  
  65. //swap
  66. t = masyvas[end];
  67. masyvas[end] = masyvas[pind];
  68. masyvas[pind] = t;
  69.  
  70. Kvs = Kvs + 3;
  71. return pind;
  72. }
  73.  
  74. // spartusis rusiavimo algorimas (Quick sort)
  75. void SpartusisAlgoritmas(vector<int> &masyvas, int start, int end) {
  76.  
  77. if (start<end)
  78. {
  79. int pivot_ind = partition(masyvas, start, end);
  80. SpartusisAlgoritmas(masyvas, start, pivot_ind - 1);
  81. SpartusisAlgoritmas(masyvas, pivot_ind + 1, end);
  82. }
  83. }
  84.  
  85. void Duom_seka(vector<int> &masyvas, int N)
  86. {
  87. // generuojame masyva:
  88. for (int i = 1; i <= N; i++)
  89. masyvas.push_back(i);
  90.  
  91. // inicializuojame atsitiktiniu skaiciu generatoriu:
  92. srand(N);
  93. // Atsitiktinai sumaisome masyva:
  94. random_shuffle(masyvas.begin(), masyvas.end());
  95. }
  96.  
  97. // Iterpimo r.a. - laiko matavimas
  98. void Iterpimo_laiko_mat(int N, int K)
  99. {
  100. vector<int> masyvas;
  101. Duom_seka(masyvas, N);
  102.  
  103. clock_t start = clock(); // matuojam laika
  104. for (int k = 0; k < K; k++) // kartojimu ciklas laiku matavimui
  105. {
  106. IterpimoAlgoritmas(masyvas);
  107. }
  108. clock_t end = clock();
  109. double laikas = (double)(end - start) / (CLOCKS_PER_SEC * K) * 1000;
  110.  
  111. cout << ", laikas = " << laikas << " (ms)" << endl;
  112. }
  113.  
  114.  
  115. // Spartusis r.a. - laiko matavimas
  116. void Spartusis_laiko_mat(int N, int K)
  117. {
  118. vector<int> masyvas;
  119. Duom_seka(masyvas, N);
  120.  
  121. clock_t start = clock(); // matuojam laika
  122. for (int k = 0; k < K; k++) // kartojimu ciklas laiku matavimui
  123. {
  124. SpartusisAlgoritmas(masyvas, 0, masyvas.size() - 1);
  125. }
  126.  
  127. clock_t end = clock();
  128. double laikas = (double)(end - start) / (CLOCKS_PER_SEC * K) * 1000;
  129.  
  130. cout << ", laikas = " << laikas << " (ms)" << endl;
  131. }
  132.  
  133.  
  134. // Iterpimo r.a. - kopijavimu ir palyginimu skaiciu matavimas
  135. void Iterpimo_VS_mat(int &Pvs, int &Kvs, int N)
  136. {
  137. vector<int> masyvas;
  138. Duom_seka(masyvas, N);
  139.  
  140. IterpimoAlgoritmas(masyvas);
  141.  
  142. cout << "Kai N = " << N << ", palyginimu VS = " << Pvs << ", kopijavimu VS = " << Kvs;
  143. }
  144.  
  145. // Spartusis r.a. - kopijavimu ir palyginimu skaiciu matavimas
  146. void Spartusis_VS_mat(int &Pvs, int &Kvs, int N)
  147. {
  148. vector<int> masyvas;
  149. Duom_seka(masyvas, N);
  150.  
  151. SpartusisAlgoritmas(masyvas, 0, masyvas.size() - 1);
  152.  
  153. cout << "Kai N = " << N << ", palyginimu VS = " << Pvs << ", kopijavimu VS = " << Kvs;
  154. }
  155.  
  156. int main()
  157. {
  158. int N = 0, K=10000; // aibes elementu skaicius
  159.  
  160. cout << "Iterpimo rusiavimo algoritmas\n\n";
  161. for (int i = 0; i < 8; i++)
  162. {
  163. N = N + 100;
  164. Pvs = 0;
  165. Kvs = 0;
  166. Iterpimo_VS_mat(Pvs, Kvs, N);
  167. Iterpimo_laiko_mat(N,K);
  168. }
  169.  
  170. N = 0;
  171. cout << "\n\nSpartusis rusiavimo algoritmas\n\n";
  172. for (int i = 0; i < 8; i++)
  173. {
  174. N = N + 100;
  175. Pvs = 0;
  176. Kvs = 0;
  177. Spartusis_VS_mat(Pvs, Kvs, N);
  178. Spartusis_laiko_mat(N,K);
  179. }
  180.  
  181. return 0;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement