Ćwiczenia

Zadanie 1

Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi \( \lceil \log 4! \rceil \).

Zadanie 2

Zaproponuje algorytm sortujący 4 elementy za pomocą co 5 porównań.

Zadanie 3

Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.

Zadanie 4

Udowodnij, że każdy algorytm wyznaczający element minimalny w zbiorze \( n \)-elementowym wykonuje w pesymistycznym przypadku co najmniej \( n-1 \) porównań.

Zadanie 5

Zaproponuj algorytm, który w ciągu długości \( n \) wyznacza elementy maksymalmy i minimalny wykonując co najwyżej \( 3n/2 - 2 \) porównania, gdy \( n \) jest parzyste, a co najwyżej \( 3\lfloor n/2\rfloor \), gdy \( n \) jest nieparzyste.