API tools faq
paste
Sanady

Tutorial 5

Sanady
Oct 22nd, 2019
304
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.13 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. Meno a priezvisko:
  3.  
  4. POKYNY:
  5. (1)  Subor premenujte na Priezvisko_Meno_ID_du05.cpp (pouzite vase udaje bez diakritiky).
  6. (2)  Implementujte funkcie tak, aby splnali popis pri ich deklaraciach.
  7. (3)  Cela implementacia musi byt v tomto jednom subore.
  8. (4)  Odovzdajte len tento (spravne premenovany) zdrojovy subor.
  9. (5)  Program musi byt kompilovatelny.
  10. (6)  Globalne a staticke premenne su zakazane.
  11. (7)  V ziadnom pripade nemente deklaracie funkcii, ktore mate za ulohu naprogramovat
  12.      (nemente nazvy, navratove hodnoty ani typ a pocet parametrov v zadanych funkciach).
  13.      Nemente implementacie zadanych datovych typov, ani implementacie hotovych pomocnych funkcii.
  14. (8)  V pripade potreby mozete kod doplnit o dalsie pomocne funkcie alebo struktury.
  15. (9)  Vase riesenie otestujte (vo funkcii 'main' a pomocou doplnenych pomocnych funkcii alebo struktur).
  16.      Testovaci kod ale nebude hodnoteny.
  17. (10) Funkcia 'main' musi byt v zdrojovom kode posledna.
  18. */
  19.  
  20. #include <iostream>
  21.  
  22. using namespace std;
  23.  
  24. //-------------------------------------------------------------------------------------------------
  25. // ULOHA (0.2 boda)
  26. //-------------------------------------------------------------------------------------------------
  27. /*
  28.     Prida novy prvok do heapu.
  29.     Verzia heap-u je Min-heap (hodnota kazdeho uzla je mensia alebo rovna ako hodnoty vsetkych jeho nasledovnikov).
  30.     Pouzije algoritmus sift up.
  31.  
  32.     PARAMETRE:
  33.         [in, out] data - heap, do ktoreho prida novy prvok
  34.         [in] addIndex - index prvku, ktory prida do heap-u (preusporiadanim prvkov)
  35.  
  36.     VSTUPNE PODMIENKY:
  37.         Prvky data[0]...data[addIndex-1] (vratane) tvoria heap
  38.         'data' ukazuje na platne pole
  39.         'addIndex' moze mat lubovolnu hodnotu
  40.  
  41.     VYSTUPNE PODMIENKY:
  42.         Prvky data[0]...data[addIndex] (vratane) tvoria heap
  43.         Preusporiada prvky data[0]...data[addIndex] tak, aby tvorili heap
  44.  
  45.     PRIKLADY:
  46.         vstup:  data = {2, 4, 10, 7, 1, 2, 5, 0, 3, -1, 11, 12, 1}, addIndex = 4
  47.         vystup: data = {1, 2, 10, 7, 4, 2, 5, 0, 3, -1, 11, 12, 1}
  48.  
  49.         vstup:  data = {3, 4, 10, 5, 5, 11, 15, 7, 8, 9, 10, 14,  8, 1, 2}, addIndex = 12
  50.         vystup: data = {3, 4,  8, 5, 5, 10, 15, 7, 8, 9, 10, 14, 11, 1, 2}
  51. */
  52. void siftUp(int data[], const size_t addIndex)
  53. {
  54.     // TODO
  55. }
  56.  
  57. //-------------------------------------------------------------------------------------------------
  58. // ULOHA (0.2 boda)
  59. //-------------------------------------------------------------------------------------------------
  60. /*
  61.     Vytvori heap na poli 'data' preusporiadanim prvkov.
  62.     Verzia heap-u je Min-heap (hodnota kazdeho uzla je mensia alebo rovna ako hodnoty vsetkych jeho nasledovnikov).
  63.     Pouzije algoritmus sift up.
  64.  
  65.     PARAMETRE:
  66.         [in, out] data - pole, ktore funkcia preusporiada, aby bolo heap-om
  67.         [in] length - pocet prvkov pola
  68.  
  69.     VSTUPNE PODMIENKY:
  70.         'data' ukazuje na platne pole, ak 'length' > 0
  71.         'length' moze mat lubovolnu hodnotu
  72.  
  73.     VYSTUPNE PODMIENKY:
  74.         'data' je heap-om
  75.  
  76.     PRIKLAD:
  77.         vstup:  data = {7, 2, 1, 2, 8, 5, 3, 4, 2, 2, 6}, length = 11
  78.         vystup: data = {1, 2, 2, 2, 2, 5, 3, 7, 4, 8, 6}
  79. */
  80. void buildHeapSiftUp(int data[], const size_t length)
  81. {
  82.     // TODO
  83. }
  84.  
  85. //-------------------------------------------------------------------------------------------------
  86. // ULOHA (0.2 boda)
  87. //-------------------------------------------------------------------------------------------------
  88. /*
  89.     Opravi cast heap-u (podstrom ktoreho koren ma index 'topIndex')
  90.     Verzia heap-u je Min-heap (hodnota kazdeho uzla je mensia alebo rovna ako hodnoty vsetkych jeho nasledovnikov).
  91.     Pouzite algoritmus sift down.
  92.  
  93.     PARAMETRE:
  94.         [in, out] data - pole, v ktorom funkcia opravi cast heapu preusporiadanim prvkov
  95.         [in] topIndex - index korena podstromu (casti heapu), ktory sa ma opravit
  96.         [in] length - pocet prvkov pola
  97.  
  98.     VSTUPNE PODMIENKY:
  99.         Podstromy prvku s indexom 'topIndex' splnaju podmienky heap (podstromy, ktorych korene su priamy nasledovnici uzla s indexom 'topIndex').
  100.         'data' ukazuje na platne pole
  101.         'topIndex' moze mat lubovolnu hodnotu
  102.         'length' moze mat lubovolnu hodnotu
  103.  
  104.     VYSTUPNE PODMIENKY:
  105.         Podstrom, ktoreho koren ma index 'topIndex' splna podmienku heap.
  106.  
  107.     PRIKLADY:
  108.         vstup:  data = {55, 20, 10, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140}, topIndex = 0, length = 15
  109.         vystup: data = {10, 20, 50, 30, 40, 55, 60, 70, 80, 90, 100, 110, 120, 130, 140}
  110.  
  111.         vstup:  data = {100, 8, 2, 1, 0, 5, 6, 7, 4, 2, 3, 11, 12, 13, 14, 15, 16, 17}, topIndex = 1, length = 18
  112.         vystup: data = {100, 0, 2, 1, 2, 5, 6, 7, 4, 8, 3, 11, 12, 13, 14, 15, 16, 17}
  113. */
  114. void siftDown(int data[], const size_t topIndex, const size_t length)
  115. {
  116.     // TODO
  117. }
  118.  
  119. //-------------------------------------------------------------------------------------------------
  120. // ULOHA (0.2 boda)
  121. //-------------------------------------------------------------------------------------------------
  122. /*
  123.     Vytvori heap na poli 'data' preusporiadanim prvkov.
  124.     Verzia heap-u je Min-heap (hodnota kazdeho uzla je mensia alebo rovna ako hodnoty vsetkych jeho nasledovnikov).
  125.     Pouzitej algoritmus sift down.
  126.  
  127.     PARAMETRE:
  128.         [in, out] data - pole, ktore funkcia preusporiada aby bolo heap-om
  129.         [in] length - pocet prvkov pola
  130.  
  131.     VSTUPNE PODMIENKY:
  132.         'data' ukazuje na platne pole, ak 'length' > 0
  133.         'length' moze mat lubovolnu hodnotu
  134.  
  135.     VYSTUPNE PODMIENKY:
  136.         'data' je heap-om
  137.  
  138.     PRIKLAD:
  139.         vstup:  data = {7, 2, 1, 2, 8, 5, 3, 4, 2, 2, 6}, length = 11
  140.         vystup: data = {1, 2, 3, 2, 2, 5, 7, 4, 2, 8, 6}
  141. */
  142. void buildHeapSiftDown(int data[], const size_t length)
  143. {
  144.     // TODO
  145. }
  146.  
  147. //-------------------------------------------------------------------------------------------------
  148. // ULOHA (0.2 boda)
  149. //-------------------------------------------------------------------------------------------------
  150. /*
  151.     Preusporiada pole 'data' od najvacsieho prvku po najmensi.
  152.     Pouzite algoritmus heap sort.
  153.  
  154.     PARAMETRE:
  155.         [in,out] data - pole, ktore funkcia usporiada
  156.         [in] length - dlzka pola
  157.  
  158.     VSTUPNE PODMIENKY:
  159.         'data' ukazuje na platne pole, ak 'length' > 0
  160.         'length' moze mat lubovolnu hodnotu
  161.  
  162.     VYSTUPNE PODMIENKY:
  163.         Pole 'data' je usporiadane
  164.  
  165.     PRIKLAD:
  166.         vstup:  data = {7, 2, 1, 2, 8, 5, 3, 4, 2, 2, 6}, length = 11
  167.         vystup: data = {8, 7, 6, 5, 4, 3, 2, 2, 2, 2, 1}
  168. */
  169. void heapSort(int data[], const size_t length)
  170. {
  171.     // TODO
  172. }
  173.  
  174. //-------------------------------------------------------------------------------------------------
  175. // TUTORIAL
  176. //-------------------------------------------------------------------------------------------------
  177.  
  178. #define ARRAY_SIZE(arr)(sizeof(arr)/arr[0])
  179.  
  180. void siftDown(int* data, int start, int end)
  181. {
  182.     int iLeftChild = start*2 + 1;
  183.     int iRightChild = start*2 + 2;
  184.     int tmp = start;
  185.  
  186.     if(iLeftChild <= end && data[iLeftChild] > data[tmp])
  187.     {
  188.         tmp = iLeftChild;
  189.     }
  190.  
  191.     if(iRightChild <= end && data[iRightChild] > data[tmp])
  192.     {
  193.         tmp = iRightChild;
  194.     }
  195.  
  196.     if(tmp != start)
  197.     {
  198.         swap(data[start], data[tmp]);
  199.         siftDown(data, tmp, end);
  200.     }
  201. }
  202.  
  203. void buildHeapSiftDown(int* data, int n)
  204. {
  205.     for(int i = n/2-1; i >= 0 ; i--)
  206.     {
  207.         siftDown(data, i, n - 1);
  208.     }
  209. }
  210.  
  211. void heapSort(int* data, int n)
  212. {
  213.     //1. faza
  214.     buildHeapSiftDown(data, n);
  215.     //2. faza
  216.     while(n > 1)
  217.     {
  218.         //extrakcia maxima
  219.         swap(data[0], data[n-1]);
  220.         n--;
  221.         siftDown(data, 0, n-1);
  222.     }
  223. }
  224.  
  225. //-------------------------------------------------------------------------------------------------
  226. // TESTOVANIE
  227. //-------------------------------------------------------------------------------------------------
  228.  
  229. // tu mozete doplnit pomocne testovacie funkcie a struktury
  230.  
  231. int main() {
  232.  
  233.     // tu mozete doplnit testovaci kod
  234.     int data[20];
  235.     generateArray(data, 20);
  236.     heapSort(data, 20);
  237.     printArray(data, 20);
  238.     return 0;
  239. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!