SHARE
TWEET

Untitled

a guest Oct 13th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include "Profiler.h"
  3. #include "Profiler.h"
  4.  
  5. #define AVG_BUBBLE_COMP "avg_bubble_comp"
  6. #define AVG_BUBBLE_ASSIG "avg_bubble_assig"
  7. #define AVG_BUBBLE_OP "avg_bubble_operations"
  8.  
  9. #define AVG_INSERTION_COMP "avg_insertion_comp"
  10. #define AVG_INSERTION_ASSIG "avg_insertion_assig"
  11. #define AVG_INSERTION_OP "avg_insertion_operations"
  12.  
  13. #define AVG_SELECTION_COMP "avg_selection_comp"
  14. #define AVG_SELECTION_ASSIG "avg_selection_assig"
  15. #define AVG_SELECTION_OP "avg_selection_operations"
  16.  
  17. #define BEST_BUBBLE_COMP "best_bubble_comp"
  18. #define BEST_BUBBLE_ASSIG "best_bubble_assig"
  19. #define BEST_BUBBLE_OP "best_bubble_op"
  20.  
  21. #define BEST_INSERTION_COMP "best_insertion_comp"
  22. #define BEST_INSERTION_ASSIG "best_insertion_assig"
  23. #define BEST_INSERTION_OP "best_insertion_op"
  24.  
  25. #define BEST_SELECTION_COMP "best_selection_comp"
  26. #define BEST_SELECTION_ASSIG "best_selection_assig"
  27. #define BEST_SELECTION_OP "best_selection_op"
  28.  
  29. #define WORST_BUBBLE_COMP "worst_bubble_comp"
  30. #define WORST_BUBBLE_ASSIG "worst_bubble_assig"
  31. #define WORST_BUBBLE_OP "worst_bubble_op"
  32.  
  33. #define WORST_SELECTION_COMP "worst_selection_comp"
  34. #define WORST_SELECTION_ASSIG "worst_selection_assig"
  35. #define WORST_SELECTION_OP "worst_selection_op"
  36.  
  37. #define WORST_INSERTION_COMP "worst_insertion_comp"
  38. #define WORST_INSERTION_ASSIG "worst_insertion_assig"
  39. #define WORST_INSERTION_OP "worst_insertion_op"
  40.  
  41. using namespace std;
  42. Profiler profiler("sort");
  43.  
  44. int comp_bubble, comp_insert, comp_sel, assig_bubble, assig_insert, assig_sel, op_bubble, op_insert, op_sel;
  45. void printArray(int* a, int n)
  46. {
  47.     for (int i = 0; i < n; i++)
  48.         cout << a[i] << " ";
  49.     cout << "\n";
  50.  
  51. }
  52. void bubbleSort(int* a, int n)
  53. {
  54.     assig_bubble = 0;
  55.     comp_bubble = 0;
  56.     int i, j, aux;
  57.     for (i = 0; i < n; i++)
  58.     {
  59.         for (j = 0; j < n - i - 1; j++)
  60.         {
  61.             if (a[j] > a[j + 1])
  62.             {
  63.                 aux = a[j];
  64.                 a[j] = a[j + 1];
  65.                 a[j + 1] = aux;
  66.                 assig_bubble += 3;
  67.             }
  68.             comp_bubble++;
  69.         }
  70.         //printArray(a, 5);
  71.     }
  72.     //op_bubble = comp_bubble + assig_bubble;
  73. }
  74. void selectionSort(int* a, int n)
  75. {
  76.     assig_sel = 0;
  77.     comp_sel = 0;
  78.     int buff, aux;
  79.     for (int i = 0; i < n - 1; i++)
  80.     {
  81.         buff = i + 1;
  82.         for (int j = i + 2; j < n; j++)
  83.         {
  84.             if (a[buff] > a[j]) buff = j;
  85.    
  86.             comp_sel++;
  87.  
  88.         }
  89.         if (a[i] < a[buff])
  90.         {
  91.             aux = a[i + 1];
  92.             a[i + 1] = a[buff];
  93.             a[buff] = aux;
  94.             assig_sel += 3;
  95.         }
  96.         else
  97.         {
  98.             aux = a[i];
  99.             a[i] = a[buff];
  100.             a[buff] = aux;
  101.             assig_sel += 3;
  102.         }
  103.         comp_sel++;
  104.     }
  105. }
  106. void insertionSort(int* a, int n)
  107. {
  108.     assig_insert = 0;
  109.     comp_insert = 0;
  110.     int buff, j;
  111.     for (int i = 1; i < n; i++)
  112.     {
  113.         buff = a[i];
  114.         assig_insert++;
  115.         j = i - 1;
  116.         while (j >= 0 && buff < a[j])
  117.         {
  118.             a[j + 1] = a[j];
  119.             assig_insert++;
  120.             j--;
  121.         }
  122.         comp_insert++;
  123.         a[j + 1] = buff;
  124.         assig_insert++;
  125.     }
  126.  
  127. }
  128. void demoBubble()
  129. {
  130.     cout << "Demo Bubble" << "\n";
  131.     int a[5] = { 9,3,7,11,12 };
  132.     bubbleSort(a, 5);
  133.     printArray(a, 5);
  134. }
  135. void demoSelection()
  136. {
  137.     cout << "\n" << "Demo Selection" << "\n";
  138.     int a[5] = { 9,3,7,11,12 };
  139.     selectionSort(a, 5);
  140.     printArray(a, 5);
  141. }
  142. void demoInsertion()
  143. {
  144.     int n = 5;
  145.     cout << "\n" << "Demo Insertion" << "\n";
  146.     int a[5] = { 9,3,7,11,12 };
  147.     insertionSort(a, n);
  148.     printArray(a, n);
  149.  
  150. }
  151. int* generateAvgCase(int n)
  152. {
  153.     int* a = (int*)malloc(n * sizeof(int));
  154.     FillRandomArray(a, n);
  155.     return a;
  156. }
  157. int* generateAscendingOrder(int n)
  158. {
  159.     int* a = (int*)malloc(n * sizeof(int));
  160.     FillRandomArray(a, n, 10, 300, false, 1);
  161.     return a;
  162. }
  163. int* generateDescendingOreder(int n)
  164. {
  165.     int* a = (int*)malloc(n * sizeof(int));
  166.     FillRandomArray(a, n, 10, 300, false, 2);
  167.     return a;
  168. }
  169. void generateGraphs()
  170. {
  171.     //avg case for bubble sort
  172.     for (int size = 100; size <= 10000; size += 500)
  173.     {
  174.         int* a = generateAvgCase(size);
  175.         bubbleSort(a, size);
  176.         profiler.countOperation(AVG_BUBBLE_COMP, size, comp_bubble);
  177.         profiler.countOperation(AVG_BUBBLE_ASSIG, size, assig_bubble);
  178.         profiler.addSeries(AVG_BUBBLE_OP, AVG_BUBBLE_COMP, AVG_BUBBLE_ASSIG);
  179.         free(a);
  180.  
  181.         a = generateAvgCase(size);
  182.         selectionSort(a, size);
  183.         profiler.countOperation(AVG_SELECTION_COMP, size, comp_sel);
  184.         profiler.countOperation(AVG_SELECTION_ASSIG, size, assig_sel);
  185.         profiler.addSeries(AVG_SELECTION_OP, AVG_SELECTION_COMP, AVG_SELECTION_ASSIG);
  186.         free(a);
  187.  
  188.         a = generateAvgCase(size);
  189.         insertionSort(a, size);
  190.         profiler.countOperation(AVG_INSERTION_COMP, size, comp_insert);
  191.         profiler.countOperation(AVG_INSERTION_ASSIG, size, assig_insert);
  192.         profiler.addSeries(AVG_INSERTION_OP, AVG_INSERTION_COMP, AVG_INSERTION_ASSIG);
  193.         free(a);
  194.  
  195.         profiler.createGroup("Average Case Op", AVG_BUBBLE_OP, AVG_SELECTION_OP, AVG_INSERTION_OP);
  196.         profiler.createGroup("Average Case Assig", AVG_BUBBLE_ASSIG, AVG_SELECTION_ASSIG, AVG_INSERTION_ASSIG);
  197.         profiler.createGroup("Average Case Comp", AVG_BUBBLE_COMP, AVG_SELECTION_COMP, AVG_INSERTION_COMP);
  198.  
  199.  
  200.         ///best cases
  201.         a = generateAscendingOrder(size);
  202.         bubbleSort(a, size);
  203.         profiler.countOperation(BEST_BUBBLE_COMP, size, comp_bubble);
  204.         profiler.countOperation(BEST_BUBBLE_ASSIG, size, assig_bubble);
  205.         profiler.addSeries(BEST_BUBBLE_OP, BEST_BUBBLE_COMP, BEST_BUBBLE_ASSIG);
  206.         free(a);
  207.  
  208.         a = generateAscendingOrder(size);
  209.         selectionSort(a, size);
  210.         profiler.countOperation(BEST_BUBBLE_COMP, size, comp_sel);
  211.         profiler.countOperation(BEST_BUBBLE_ASSIG, size, assig_sel);
  212.         profiler.addSeries(BEST_SELECTION_OP, BEST_SELECTION_COMP, BEST_SELECTION_ASSIG);
  213.         free(a);
  214.  
  215.         a = generateAscendingOrder(size);
  216.         insertionSort(a, size);
  217.         profiler.countOperation(BEST_INSERTION_COMP, size, comp_insert);
  218.         profiler.countOperation(BEST_INSERTION_ASSIG, size, assig_insert);
  219.         profiler.addSeries(BEST_INSERTION_OP, BEST_INSERTION_COMP, BEST_INSERTION_ASSIG);
  220.         free(a);
  221.  
  222.         profiler.createGroup("Best Case Comp", BEST_BUBBLE_COMP, BEST_SELECTION_COMP, BEST_INSERTION_COMP);
  223.         profiler.createGroup("Best Case Assig", BEST_BUBBLE_ASSIG, BEST_SELECTION_ASSIG, BEST_INSERTION_ASSIG);
  224.         profiler.createGroup("Best Case Op", BEST_BUBBLE_OP, BEST_SELECTION_OP, BEST_INSERTION_OP);
  225.  
  226.  
  227.         ///worst cases
  228.         a = generateDescendingOreder(size);
  229.         bubbleSort(a, size);
  230.         profiler.countOperation(WORST_BUBBLE_COMP, size, comp_bubble);
  231.         profiler.countOperation(WORST_BUBBLE_ASSIG, size, assig_bubble);
  232.         profiler.addSeries(WORST_BUBBLE_OP, WORST_BUBBLE_COMP, WORST_BUBBLE_ASSIG);
  233.         free(a);
  234.  
  235.         a = generateDescendingOreder(size);
  236.         selectionSort(a, size);
  237.         profiler.countOperation(WORST_SELECTION_COMP, size, comp_sel);
  238.         profiler.countOperation(WORST_SELECTION_ASSIG, size, assig_sel);
  239.         profiler.addSeries(WORST_SELECTION_OP, WORST_SELECTION_COMP, WORST_SELECTION_ASSIG);
  240.         free(a);
  241.  
  242.         a = generateDescendingOreder(size);
  243.         insertionSort(a, size);
  244.         profiler.countOperation(WORST_INSERTION_COMP, size, comp_insert);
  245.         profiler.countOperation(WORST_INSERTION_ASSIG, size, assig_insert);
  246.         profiler.addSeries(WORST_INSERTION_OP, WORST_INSERTION_COMP, WORST_INSERTION_ASSIG);
  247.         free(a);
  248.  
  249.  
  250.         profiler.createGroup("Worst Case Comp", WORST_BUBBLE_COMP, WORST_SELECTION_COMP, WORST_INSERTION_COMP);
  251.         profiler.createGroup("Worst Case Assig", WORST_BUBBLE_ASSIG, WORST_SELECTION_ASSIG, WORST_INSERTION_ASSIG);
  252.         profiler.createGroup("Worst Case Op", WORST_BUBBLE_OP, WORST_SELECTION_OP, WORST_INSERTION_OP);
  253.     }
  254. }
  255. int main()
  256. {
  257.  
  258.     //demoBubble();
  259.     //demoInsertion();
  260.     //demoSelection();
  261.     generateGraphs();
  262.     profiler.showReport();
  263.     //printArray(a, 5);
  264.     return 0;
  265. }
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