7. cvičení - 13.11.2009

• rozděl a panuj
• třídění
  • porovnáváním
    • merge sort (rozděl a panuj)
      • [proč má složitost O(n*log(n))?]
      • ukázkový zdroják
    • 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 - 1, 2
    • insert sort
      • O(n^2) v nejhorším případě
      • ukázkový zdroják
    • select sort
      • O(n^2) v nejhorším případě
      • ukázkový zdroják
    • bubble sort
      • O(n^2) v nejhorším i nejlepším (!) případě
      • ukázkové zdrojáky - 1, 2
  • bez porovnávání - lepší než n*log(n)
    • count sort
    • bucket sort
      • ukázkový zdroják
    • radix sort - aplikace na 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)
    • popsáno ve slajdech na ADS 1 od doc. Ondřeje Čepka
  • ukázkový zdroják
  • dále: medián = N/2-tý prvek
• výrazy
  • strom výrazu
    • vyhodnocení
  • gramatika pro infix → nepřímá rekurze
  • infix/postfix/prefix
  • převody notace pomocí stromu
  • ukázkové zdrojáky

Ukázkové zdrojáky jsou od doc. Pavla Töpfera.