Ostré meze a 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 řekli si 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, ukázali jeho pseudokód, průběh na příkladu a jeho modifikace. Zdůvodnili jsme si jejich složitosti.

Zbytek hodiny jsme programovali.

Úkoly

1. Sestavte obdobnou hierarchii funkcí jako minule, 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.
3. Implementujte Shaker/Cocktail sort v jazyce C.
4. Implementujte v jazyce C vylepšení bubble sortu s využitím znalosti o posledním prohození v předchozí iteraci.