Porównanie algorytmów sortujących. Drzewa decyzyjne.
Algorytm sortujący za pomocą porównań można przedstawić w
algorytm pesymistyczny czas działania
postaci drzewa decyzyjnego. Jest to drzewo binarne, które węzły
przez wstawianie Åš(n2)
odpowiadają porównaniom wykonywanym przez algorytm dla
przez scalanie O(n log n)
danych ustalonego rozmiaru.
przez kopcowanie O(n log n)
quicksort O(n2) (średnio O(n log n)) Każdy węzeł wewnętrzny ma etykietę i : j dla pewnych
1 d" i, j d" n, a z każdym liściem związana jest permutacja
Wszystkie cztery algorytmy mają wspólną cechę: porządek, który
(Ą(1), Ą(2), . . . , Ą(n)). Wykonanie algorytmu odpowiada przejściu
wyznaczają jest oparty tylko i wyłącznie na wynikach porównań
ścieżki od korzenia do jednego z liści. W każdym węz
le
między elementami. Takie algorytmy nazywamy algorytmami
wewnętrznym wykonywane jest porównanie ai z aj. W lewym
sortującymi za pomocą porównań.
poddrzewie znajdują się porównania wykonywane przez algorytm,
jeśli okaże się że ai d" aj, a prawe poddrzewo zawiera porównania
Pokażemy, że każdy algorytm sortujący za pomocą porównań musi
wykonywane w przeciwnym wypadku, to jest gdy ai > aj. Jeśli
w przypadku pesymistycznym wykonać &!(n log n) porównań, żeby
dochodzimy do liścia, oznacza to algorytm znalazł juz
posortować ciąg n elementów.
uporzÄ…dkowanie aÄ„(1) d" aÄ„(2) d" · · · d" aÄ„(n).
Przykład. Dolne ograniczenie na pesymistyczny czas sortowania.
Drzewo decyzyjne dla algorytmu sortowania przez wstawianie dla
ciągu 3-elementowego. Czerwona ścieżka odpowiada działaniu Ponieważ poprawny algorytm sortujący musi umożliwiać
algorytmu dla ciągu wejściowego (a1 = 5, a2 = 7, a3 = 2). otrzymanie każdej permutacji swoich danych wejściowych, zatem
Permutacja (3, 1, 2) w liściu oznacza, że wynikiem algorytmu jest każda spośród n! permutacji zbioru indeksów musi wystąpić jako
ciąg a3 = 2 d" a1 = 5 d" a2 = 7. jeden z liści w drzewie decyzyjnym.
Długość najdłuższej ścieżki od korzenia drzewa decyzyjnego do
1 : 2
d"
>
dowolnego liścia odpowiada pesymistycznej liczbie porównań
wykonywanych przez algorytm sortujÄ…cy. StÄ…d pesymistyczna
2 : 3 1 : 3
liczba porównań dla danego algorytmu sortującego za pomocą
porównań jest równa wysokości jego drzewa decyzyjnego.
> >
d" d"
(1, 2, 3) (2, 1, 3)
1 : 3 2 : 3 Twierdzenie 9.1
Dowolny algorytm sortujący n elementów za pomocą porównań w
> >
d" d"
przypadku pesymistycznym wymaga &!(n log n) porównań.
(1, 3, 2) (3, 1, 2) (2, 3, 1) (3, 2, 1)
Lemat 9.2
log(n!) = Åš(n log n).
Dowód Twierdzenia 9.1
Dowód Lematu 9.2. Pokażemy, że nn e" n! e" nn/2.
Maksymalna liczba porównań jest równa wysokości drzewa
Pierwsza nierówność jest trywialna: n! = 1 · · · n d" nn, bo każdy z
decyzyjnego.
n czynników jest nie większy niż n.
Oznaczmy tą wysokość przez h, a liczbę liści przez k.
Aby wykazać drugą nierówność, zauważmy że:
Ponieważ każda permutacja zbioru indeksów występuje w pewnym
n

liściu, więc k e" n!.
(n!)2 = (1 · · · n)(n · · · 1) = i(n - i + 1).
i=1
Drzewo binarne o wysokości h ma co najwyżej 2h liści, zatem
Potraktujmy i(n - i + 1) jako funkcjÄ™ kwadratowÄ… zmiennej i.
2h e" k e" n!,
Funkcja ta przyjmuje wartość najmniejszą w przedziale [1..n] na
jednym z końców przedziału, bo współczynnik przy i2 jest ujemny,
a stÄ…d
więc parabola nie ma minimum. Zatem i(n - i + 1) e" n dla
h e" log(n!).
i = 1, . . . , n, a stad (n!)2 e" nn.
Na mocy Lematu 9.2 log(n!) = Åš(n log n), a zatem h = &!(n log n).
Po zlogarytmowaniu nierówności nn e" n! e" nn/2 otrzymujemy
n log n
n log n e" log(n!) e" .
2
Wniosek 9.3
Sortowanie przez scalanie i sortowanie przez kopcowanie sÄ…
asymptotycznie optymalnymi algorytmami sortujÄ…cymi za pomocÄ…
porównań.
Dowód. Górne ograniczenie O(n log n) pesymistycznego czasu
działania tych algorytmów jest zgodne z dolnym ograniczeniem
&!(n log n) z Twierdzania 9.1.