====== 7. cvičení - 13.11.2009 ======

===== Co jsme dělali? =====

  * [[wp>/Divide_and_conquer_algorithm|rozděl a panuj]]
  * [[wp>Sorting_algorithm|třídění]]
    * porovnáváním
      * [[wp>Merge_sort|merge sort]] (rozděl a panuj)
        * [proč má složitost O(n*log(n))?]
        * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/MERGE.PAS|ukázkový zdroják]]
      * [[wp>Quick_sort|quick sort]] (rozděl a panuj)
        * O(n^2) v nejhorším případě
        * O(n*log(n)) v průměrném případě
        * ukázkové zdrojáky - [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/QUICK1.PAS|1]], [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/QUICK1v.PAS|2]]
      * [[wp>Insert_sort|insert sort]]
        * O(n^2) v nejhorším případě
        * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/PR_VKLAD.PAS|ukázkový zdroják]]
      * [[wp>Select_sort|select sort]]
        * O(n^2) v nejhorším případě
        * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/PR_VYBER.PAS|ukázkový zdroják]]
      * [[wp>Bubble_sort|bubble sort]]
        * O(n^2) v nejhorším i nejlepším (!) případě
        * ukázkové zdrojáky - [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/BUBLINK.PAS|1]], [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/BUBLINKA.PAS|2]]
    * bez porovnávání - lepší než n*log(n)
      * [[wp>Count_sort|count sort]]
      * [[wp>Bucket_sort|bucket sort]]
        * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/PRIHRAD.PAS|ukázkový zdroják]]
      * [[wp>Radix_sort|radix sort]] - aplikace na [[wp>Lexicographical_order|lexikografické třídění]] řetězců
  * k-tý prvek z n prvků
    * hodí se na hledání mediánu pro quick sort (k = n/2)
    * triviálně: setřídit, vybrat, Theta(n*log(n))
    * lépe: rozděl a panuj (ořezaný quick sort), dělení na tři částí
    * ještě lépe: (Blum) medián mediánů při dělení na pět částí, O(n)
      * [[http://ktiml.mff.cuni.cz/~cepek/ADS1.ppt|popsáno ve slajdech na ADS 1]] od doc. Ondřeje Čepka
    * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/K_TY_NEJ.PAS|ukázkový zdroják]]
    * dále: [[wp>Median|medián]] = N/2-tý prvek
  * [[wp>Expression_(programming)|výrazy]]
    * strom výrazu
      * vyhodnocení
    * gramatika pro infix -> nepřímá rekurze
    * [[wp>Infix_notation|infix]]/[[wp>Postfix_notation|postfix]]/[[wp>Prefix_notation|prefix]]
    * převody notace pomocí stromu
    * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/NOTACE.PAS|ukázkové zdrojáky]]

Ukázkové zdrojáky jsou od [[materialy|doc. Pavla Töpfera]].