SHARE
TWEET

AISP - LV5

amarek Nov 18th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //LV 5
  2.  
  3. //1. zadatak
  4.  
  5. #include <iostream>
  6. using namespace std;
  7. const int N = 7;
  8. int NH = 0;
  9. int V[N] = { 12, 5, 4, 10, 7, 8, 11 };
  10. int zamjena = 0;
  11.  
  12. int lijevi(int i)
  13. {
  14.     int lj = 2 * i + 1;
  15.     if (lj > NH - 1 || i < 0)
  16.         return -1;
  17.     return lj;
  18. }
  19.  
  20. int desni(int i)
  21. {
  22.     int ds = 2 * i + 2;
  23.     if (ds > NH - 1 || i < 0)
  24.         return -1;
  25.     return ds;
  26. }
  27.  
  28. void zamjeni(int &a, int &b)
  29. {
  30.     int temp;
  31.     temp = a;
  32.     a = b;
  33.     b = temp;
  34.     zamjena++;
  35.     cout << "Niz nakon " << zamjena << ". zamjene: ";
  36.     for (int i = 0; i < N; i++)
  37.     {
  38.         cout << V[i] << " ";
  39.     }
  40.     cout << endl;
  41. }
  42.  
  43. void uhrpi(int i)
  44. {
  45.     int najveci = i;
  46.     int lj = lijevi(i);
  47.     int ds = desni(i);
  48.  
  49.     if (lj > -1)
  50.     {
  51.         if (V[lj] > V[i])
  52.             najveci = lj;
  53.     }
  54.  
  55.     if (ds > -1)
  56.     {
  57.         if (V[ds] > V[najveci])
  58.             najveci = ds;
  59.     }
  60.  
  61.     if (najveci != i)
  62.     {
  63.         zamjeni(V[i], V[najveci]);
  64.         uhrpi(najveci);
  65.     }
  66. }
  67.  
  68. void napraviHrpu()
  69. {
  70.     cout << "Napravi hrpu" << endl;
  71.     NH = N;
  72.     for (int i = NH / 2; i >= 0; i--)
  73.     {
  74.         uhrpi(i);
  75.     }
  76.     cout << "Napravljena hrpu" << endl;
  77. }
  78.  
  79. void heapsort()
  80. {
  81.     napraviHrpu();
  82.     int zadnji = NH - 1;
  83.     for (int i = zadnji; i >= 1; i--)
  84.     {
  85.         zamjeni(V[0], V[i]);
  86.         NH = NH - 1;
  87.         uhrpi(0);
  88.     }
  89. }
  90.  
  91. int main(void)
  92. {
  93.     heapsort();
  94.     return 0;
  95. }
  96.  
  97. //2. zadatak
  98.  
  99. /* #include <iostream>
  100. #include <cstdlib>
  101. #include <ctime>
  102. using namespace std;
  103.  
  104. void max_heap(int *V, int i, int n)
  105. {
  106.     int l = 2 * i + 1;
  107.     int r = 2 * i + 2;
  108.     int najveci;
  109.     if (l <= n - 1 && V[l] > V[i])
  110.         najveci = l;
  111.     else
  112.         najveci = i;
  113.     if (r <= n - 1 && V[r] > V[najveci])
  114.         najveci = r;
  115.     if (najveci != i)
  116.     {
  117.         int tmp = V[najveci];
  118.         V[najveci] = V[i];
  119.         V[i] = tmp;
  120.         max_heap(V, najveci, n);
  121.     }
  122. }
  123.  
  124. void hrpa(int *V, int n)
  125. {
  126.     int i;
  127.     for (i = n / 2 - 1; i >= 0; i--)
  128.         max_heap(V, i, n);
  129. }
  130.  
  131. void heap_sort(int *V, int n)
  132. {
  133.     int i;
  134.     hrpa(V, n);
  135.     for (i = n - 1; i > 0; i--)
  136.     {
  137.         int tmp = V[i];
  138.         V[i] = V[0];
  139.         V[0] = tmp;
  140.         n--;
  141.         max_heap(V, 0, n);
  142.     }
  143. }
  144.  
  145. void bubble_sort(int *V, int n)
  146. {
  147.     for (int i = 0; i < n - 1; i++)
  148.     {
  149.         int flag = 0;
  150.         for (int j = 0; j < n - 1 - i; j++)
  151.         {
  152.             if (V[j] > V[j + 1])
  153.             {
  154.                 int temp;
  155.                 temp = V[j];
  156.                 V[j] = V[j + 1];
  157.                 V[j + 1] = temp;
  158.                 flag = 1;
  159.             }
  160.         }
  161.         if (flag == 0)
  162.             break;
  163.     }
  164. }
  165.  
  166. void merge(int *V, int dg, int gg)
  167. {
  168.     int *T = new int[gg - dg + 1];
  169.     int s = (dg + gg) / 2;
  170.     int il = dg;
  171.     int id = s + 1;
  172.  
  173.     for (int i = 0; i < gg-dg + 1; i++)
  174.     {
  175.         if (il <= s && id <= gg)
  176.         {
  177.             if (V[il] < V[id])
  178.             {
  179.                 T[i] = V[il];
  180.                 il = il + 1;
  181.             }
  182.             else
  183.             {
  184.                 T[i] = V[id];
  185.                 id = id + 1;
  186.             }
  187.         }
  188.         else
  189.         {
  190.             if (il > s)
  191.             {
  192.                 T[i] = V[id];
  193.                 id = id + 1;
  194.             }
  195.             else
  196.             {
  197.                 T[i] = V[il];
  198.                 il = il + 1;
  199.             }
  200.         }
  201.     }
  202.     for (int i = dg; i <= gg; i++)
  203.     {
  204.         V[i] = T[i - dg];
  205.     }
  206.  
  207.     free(T);
  208. }
  209.  
  210. void merge_sort(int *V, int dg, int gg)
  211. {
  212.     if (dg == gg)
  213.         return;
  214.     int s = (dg + gg) / 2;
  215.     merge_sort(V, dg, s);
  216.     merge_sort(V, s + 1, gg);
  217.     merge(V, dg, gg);
  218. }
  219.  
  220. int main(void)
  221. {
  222.     const int N = 10000;
  223.     time_t t1, t2;
  224.     int *V = new int [N];
  225.  
  226.     srand(time(NULL));
  227.  
  228.     cout << "N = " << N << endl;
  229.  
  230.     for (int i = 0; i < N; i++)
  231.     {
  232.         V[i] = rand() % 100;
  233.     }
  234.  
  235.     t1 = clock();
  236.     bubble_sort(V, N);
  237.     t2 = clock();
  238.     printf("Vrijeme bubblesort-a je %dms\n", t2 - t1);
  239.  
  240.     for (int i = 0; i < N; i++)
  241.     {
  242.         V[i] = rand() % 100;
  243.     }
  244.  
  245.     t1 = clock();
  246.     heap_sort(V, N);
  247.     t2 = clock();
  248.     printf("Vrijeme heapsort-a je %dms\n", t2 - t1);
  249.  
  250.     for (int i = 0; i < N; i++)
  251.     {
  252.         V[i] = rand() % 100;
  253.     }
  254.  
  255.     t1 = clock();
  256.     merge_sort(V, 0, N-1);
  257.     t2 = clock();
  258.     printf("Vrijeme mergesort-a je %dms\n", t2 - t1);
  259.  
  260.     free(V);
  261.  
  262.     return 0;
  263. } */
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