ASD Ćwiczenia 5

Zadanie 1

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

Wskazówka

Przedstaw za pomocą drzewa decyzyjnego algorytm sortowania przez scalanie z pominięciem zbędnych porównań.

Zadanie 2

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

Wskazówka

Narysuj drzewo decyzyjne implementujące sortowanie przez scalanie. Unikaj redundantnych porównań.

Zadanie 3

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

Wskazówka

Załóżmy, że sortujemy ciąg $x_1,x_2,x_3,x_4,x_5$. Oto trzy pierwsze porównania:

1) $x_1$ z $x_2$

2) $x_3$ z $x_4$

3) porównanie mniejszych elementów z każdej z par.

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ń.

Wskazówka

Wykorzystaj fakt, że każdy $n$-wierzchołkowy graf spójny zawiera co najmniej $n-1$ krawędzi.

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.

Wskazówka

W pierwsze fazie porównuj elementy w rozłącznych parach.