SHARE
TWEET

Untitled

a guest Oct 13th, 2019 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Moldovan Vlad-Madalin 30227
  3.     S-au implementat algoritmii:
  4.         bubble sort
  5.         insertion sort
  6.         selection sort
  7.     Performanta pe cazul mediu:
  8.         bubble sort - O(n^2)
  9.  
  10.     Observatii:
  11.         Pe best case , bubble sort nu face nici o asignare .
  12.         Pe average case , cel mai rapid algoritm a fost ...
  13.         ...
  14.  
  15.  
  16.  
  17. */
  18. #include<iostream>
  19. #include "Profiler.h"
  20.  
  21. Profiler p("lab1");
  22.  
  23. using namespace std;
  24. void afisare(int v[], int n)
  25. {
  26.     for (int i = 0; i < n; i++)
  27.         cout << v[i] << " ";
  28.     cout << endl;
  29. }
  30. void bubble(int v[], int n)
  31. {
  32.     int sorted = 0;
  33.     int i, aux;
  34.     Operation comp = p.createOperation("bubble_comp", n);
  35.     Operation assign = p.createOperation("bubble_assign", n);
  36.     while (!sorted)
  37.     {
  38.         sorted = 1;
  39.         for (i = 0; i < n - 1; i++)
  40.         {
  41.             comp.count();
  42.             if (v[i] > v[i + 1])
  43.             {
  44.                 sorted = 0;
  45.                 assign.count(3);
  46.                 aux = v[i];
  47.                 v[i] = v[i + 1];
  48.                 v[i + 1] = aux;
  49.             }
  50.         }
  51.     }
  52. }
  53. void insertionSort(int v[], int n)
  54. {
  55.     int i, j, aux;
  56.     Operation comp = p.createOperation("insertion_comp", n);
  57.     Operation assign = p.createOperation("insertion_assign", n);
  58.     for (i = 1; i < n; i++)
  59.     {
  60.         aux = v[i];
  61.         assign.count();
  62.         j = i - 1;
  63.         while (j >= 0 && v[j] > aux)
  64.         {
  65.             comp.count();
  66.             v[j + 1] = v[j];
  67.             j--;
  68.         }
  69.         v[j + 1] = aux;
  70.         assign.count();
  71.         if (j >= 1)
  72.             comp.count();
  73.     }
  74. }
  75. void selectionSort(int v[], int n)
  76. {
  77.     Operation comp = p.createOperation("selection_comp", n);
  78.     Operation assign = p.createOperation("selection_assign", n);
  79.     int i, j, pozmin,aux;
  80.     for (i = 0; i < n - 1; i++)
  81.     {
  82.         pozmin = i;
  83.         for (j = i + 1; j < n; j++)
  84.         {
  85.             comp.count();
  86.             if (v[j] < v[pozmin])
  87.             {
  88.                 pozmin = j;
  89.             }
  90.             if (pozmin != i)
  91.             {
  92.                 assign.count(3);
  93.                 aux = v[i];
  94.                 v[i] = v[pozmin];
  95.                 v[pozmin] = aux;
  96.             }
  97.         }
  98.     }
  99.  
  100. }
  101. void demo()
  102. {
  103.     int v[] = { 2, -1, 5, 6, 3, 8, 4 };
  104.     int u[100];
  105.     int n = sizeof(v) / sizeof(v[0]);
  106.  
  107.     afisare(v, n);
  108.     memcpy(u, v, n * sizeof(v[0]));
  109.     bubble(u, n);
  110.     afisare(u, n);
  111.  
  112.     afisare(v, n);
  113.     memcpy(u, v, n * sizeof(v[0]));
  114.     insertionSort(u, n);
  115.     afisare(u, n);
  116.  
  117.     afisare(v, n);
  118.     memcpy(u, v, n * sizeof(v[0]));
  119.     selectionSort(u, n);
  120.     afisare(u, n);
  121.  
  122. }
  123. void perfAverage()
  124. {
  125.     int v[10000];
  126.     int u[10000];
  127.     for (int n = 100; n <= 10000; n += 100) {
  128.         for (int test = 0; test < 5; test++) {
  129.             FillRandomArray(v, n);
  130.             memcpy(u, v, n * sizeof(v[0]));
  131.             bubble(v, n);
  132.             memcpy(u, v, n * sizeof(v[0]));
  133.             insertionSort(u, n);
  134.         }
  135.         cout << n << endl;
  136.     }
  137.     p.addSeries("bubble", "bubble_comp", "bubble_assign");
  138.     p.addSeries("insertion", "insertion_comp", "bubble_assign");
  139.     p.addSeries("selection", "selection_comp", "selection_assign");
  140.     p.createGroup("view", "bubble", "insertion","selection");
  141.     p.createGroup("view_comp", "bubble_comp", "insertion_comp","selection_comp");
  142.     p.createGroup("view_assign", "bubble_assign", "insertion_assign","selection_comp");
  143.     p.showReport();
  144. }
  145. void perfBest()
  146. {
  147.     int v[10000];
  148.     int u[10000];
  149.     for (int n = 100; n <= 10000; n += 100) {
  150.         FillRandomArray(v, n, 10, 50000, false, ASCENDING);
  151.         memcpy(u, v, n * sizeof(v[0]));
  152.         bubble(v, n);
  153.         memcpy(u, v, n * sizeof(v[0]));
  154.         insertionSort(u, n);
  155.         cout << n << endl;
  156.     }
  157.     p.addSeries("bubble", "bubble_comp", "bubble_assign");
  158.     p.addSeries("insertion", "insertion_comp", "bubble_assign");
  159.     p.addSeries("selection", "selection_comp", "selection_assign");
  160.     p.createGroup("view", "bubble", "insertion", "selection");
  161.     p.createGroup("view_comp", "bubble_comp", "insertion_comp", "selection_comp");
  162.     p.createGroup("view_assign", "bubble_assign", "insertion_assign", "selection_comp");
  163.     p.showReport();
  164. }
  165. void perfWorst()
  166. {
  167.     int v[10000];
  168.     int u[10000];
  169.     for (int n = 100; n <= 10000; n += 100) {
  170.         cout << n << endl;
  171.         FillRandomArray(v, n, 10, 50000, false, DESCENDING);
  172.         memcpy(u, v, n * sizeof(v[0]));
  173.         bubble(v, n);
  174.         memcpy(u, v, n * sizeof(v[0]));
  175.         insertionSort(u, n);
  176.     }
  177.     p.addSeries("bubble", "bubble_comp", "bubble_assign");
  178.     p.addSeries("insertion", "insertion_comp", "bubble_assign");
  179.     p.createGroup("view", "bubble", "insertion");
  180.     p.createGroup("view_comp", "bubble_comp", "insertion_comp");
  181.     p.createGroup("view_assign", "bubble_assign", "insertion_assign");
  182.     p.showReport();
  183. }
  184. int main()
  185. {
  186.     demo();
  187.     /*perfAverage();
  188.     p.reset("lab1-best");
  189.     perfBest();
  190.     p.reset("lab1-worst");
  191.     perfWorst();*/
  192.  
  193.     system("pause");
  194.     return 0;
  195. }
RAW Paste Data
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
 
Top