6. cvičení

Témata hodiny

• Asymptotické meze podruhé
• Bubble sort

Průběh cvičení

• Zopakovali jsme si něco k asymptotický mezím z minula (O(g(n)), Ω(g(n)) a Θ(g(n))), podívali se na hierarchii, kterou vytvářejí na nám známých funkcích, a umístili si do ní n ⋅ log(n).

• Řekli jsme si o asymptotických ostrých mezích (o(g(n)) a ω(g(n))) a o jejich rozdílech oproti mezím neostrým. Ukázali jsme si pár příkladů:

  • n ⋅ log(n) ∈ ω(n),
  • 10 ⋅ n ∈ o(n²),
  • 2 ⋅ n ∉ o(n).

• Zopakovali jsme si myšlenku bubble sortu a ukázali jeho průběh na příkladu.

• Zbytek hodiny jste programovali.

Úkoly

1. Sestavte obdobnou hierarchii funkcí jako na hodině, ale tentokrát pro ostré meze. V čem je rozdíl? Proč jsme nedefinovali ostrou těsnou mez?
2. Implementujte bubble sort v jazyce C/Pythonu.
3. Implementujte Shaker/Cocktail sort (varianta bubble sortu, viz přednáška) v jazyce C/Pythonu.
4. Implementujte v jazyce C/Pythonu vylepšení bubble sortu s využitím znalosti o posledním prohození v předchozí iteraci (viz přednáška).