Algorytmy i Struktury Danych

2b. Sortowanie, selekcja

1. (1p.) Jaka jest najmniejsza możliwa głębokość liśćia w drzewie decyzyj-

nym odpowiadającym algorytmowi sortującemu za pomocą porównań?

2. (2p.) Wykaż, że nie istnieje algorytm sortujący, który działa w czasie

liniowym dla co najmniej połowy z n! możliwych danych permutacji dłu-
gości n. Czy odpowiedź ulegnie zmianie, jeśli zapytamy o ułamek 1/n (lub
odpowiednio: 1/2

n

) wszystkich permutacji?

3. (2p.) Udowodnij, że w pesymistycznym przypadku potrzeba 2n − 1 po-

równań aby scalić dwa posortowane ciągi n-elementowe.

4. (1p.) Zilustruj działanie Counting-Sort dla tablicy

A =< 7, 1, 3, 1, 2, 4, 5, 7, 2, 4, 3 >

5. (1p.) Wykaż, że procedura Counting-Sort sortuje stabilnie.

6. (1p.) Zmieniamy wiersz 9 w Counting-sort następująco:

9 for

j ← 1 to length[A]

Wykaż, że algorytm nadal działa poprawnie. Czy nowa wersja zapewnia
stabilność?

7. (2p.) Zaprojektuj algorytm, który dla danych n liczb całkowitych z prze-

działu od 1 do k wykonuje wstępne obliczenia, a następnie w czasie O(1)
potrafi odpowiadać ile z tych liczb jest w zadanym przedziale [a . . . b]. Czas
obliczeń wstępnych powinien być O(n + k).

8. (1p.) Które z następujących algorytmów są stabilne: insertion-sort, merge-

sort, quicksort, heap-sort? Podaj metodę, która z dowolnego algorytmu
sortowania tworzy stabilny algorytm sortujący? Ile dodatkowej pamięci i
czasu wymaga jej zastosowanie?

9. (1p.) Udowodnij przez indukcję poprawność Radix-sort. W którym miej-

scu dowodu potrzebne jest założenie, że pomocniczy algorytm sortujący
jest stabilny?

10. (2p.) Skonstruuj algorytm, który sortuje n liczb całkowitych z przedziału

od 1 do n

2

w czasie O(n).

11. (1p.) Zilustruj działanie Bucket-Sort dla tablicy:

A =< 0.79, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42 >.

12. (1p.) Jaki jest pesymistyczny czas sortowania kubełkowego? Jak zmody-

fikować algorytm aby oczekiwany czas był nadal liniowy, a czas pesymi-
styczny wynosił O(n lg n)?

13. (2p.) Wykaż, że drugi co do wielkości element spośród n liczb można wy-

znaczyć w pesymistycznym przypadku za pomocą n+⌈lg n⌉−2 porównań.

1

14. (2p.) Wykaż, że w pesymistycznym przypadku do wyznaczenia zarówno

minimum, jak maksimum z n liczb, konieczne jest ⌈3n/2⌉ − 2 porównań.
(Wskazówka: Rozważ, ile liczb może potencjalnie stanowić albo maksi-
mum, albo minimum, oraz zbadaj jak jedno porównanie może wpłynąć na
te wielkości.)

15. (1p.) Napisz iteracyjną wersję Randomized-Select.

16. (1p.) Zilustruj, jak w najgorszym przypadku zachowuje się Randomized-Select(A,1,10,1)

dla
A =< 3, 2, 9, 0, 7, 5, 4, 8, 6, 1 >.

17. (1p.) Czy Randomized-Select działa poprawnie, gdy w tablicy znajdują

się równe sobie elementy?

18. (2p.) Czy Select będzie działał w czasie liniowym, jeśli będziemy tworzyć

grupy po 7 elementów zamiast po 5 elementów? Jaka jest odpowiedź w
przypadku podziału na grupy 3-elementowe?

19. (1p.) Wykaż, że w algorytmie Select liczba elementów większych od

mediany median x oraz liczba elementów mniejszych od x jest niemniejsza
niż ⌈n/4⌉ jeśli n ≥ 38.

20. (1p.) Wykaż, że można zaimplementować algorytm quicksort tak, aby w

przypadku pesymistycznym działał w czasie O(n lg n).

21. (2p.) Przyjmij, że dany jest algorytm w postaci “czarnej skrzynki”, który

wyznacza medianę w pesymistycznym przypadku w czasie liniowym. Za-
projektuj algorytm, który używając tej “czarnej skrzynki” wyznacza do-
wolną statystykę pozycyjną w czasie liniowym.

22. (2p.) Zaprojektuj algorytm działający w czasie O(n), który dla danego

zbioru S parami różnych n kluczy oraz dodatniej liczby k ≤ n wyznacza
k liczb w S, które są najbliższe medianie S.

23. (2p.) Niech X[1 . . . n] i Y [1 . . . n] będą dwiema posortowanymi tablicami.

Podaj algorytm, który w czasie O(lg n) wyznacza medianę wszystkich 2n
elementów z obu tablic.

2