Informatyka MIMUW

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: