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.