Zadanie 1 (HeapSort - budowa kopca)
Udowodnij, że koszt budowy kopca w algorytmie HeapSort jest liniowy.
Zadanie 2 (HeapSort - łamigłówka)
Podaj zawartość tablicy 7-elementowej, dla której algorytm HeapSort wykona największą liczbę porównań.
Zadanie 3 (QuickSort - analiza, model losowej permutacji)
Rozważamy wersję algorytmu QuckSort, w którym podział jest dokonywany za pomocą poniższego algorytmu:
1 Partition(l,r)::
2 begin
3 v := a[l]; i := l; j := r+1;
4 repeat
5 //Niezmiennik: dla każdego k=l,l+1,...,i, a[k] <= v,
6 // dla każdego k=j,j+1,...,r+1, a[k] >= v,
7 // j-i >= -1.
8 repeat i := i+1 until a[i] >= v;
9 repeat j := j-1 until a[j] <= v;
10 if i < j then
11 a[i] :=: a[j];
12 until i >= j;
13 a[l] := a[j]; a[j] := v;
14 return j
15 end;
- Udowodnij, że jeżeli podtablica \( a[l..p] \) jest losową permutacją zawartych w niej elementów (każda permutacja jest jednakowoprawdopodobna), to podtablice \( a[l..j-1] \) i \( a[j+1..r] \) są też losowymi podtablicami zawartych w nich elementów.
- Przyjmijmy bez straty ogólności, że faza podziału kosztuje dokładnie \( p-l+2 \) porównań, przy \( p > l \). Uzasadnij, że następujące równanie jest równaniem na oczekiwaną liczbę porównań wykonywanych w algorytmie QuickSort.
\( \displaystyle A(0) = 0, A(1) = 1 \),
\( \displaystyle A(n) = n + 1 + \frac{1}{n}\sum_{s = 1}^n (A(s-1) + A(n-s)) \), dla \( \displaystyle n > 1 \).
- Rozwiąż powyższe równanie rekurencyjne.
Zadanie 4 (Średnia liczba porównań - dolne ograniczenie)
Udowodnij, że średnia liczba porównań niezbędnych do posortowania ciągu \( n \)-elementowego w modelu losowej permutacji wynosi co najmniej \( n\log n - 1.45n \).