Randomizacja algorytmu quicksort.
Będziemy zakładali, że dysponujemy generatorem liczb losowych
Wprowadz
my losowość do algorytmu quicksort. RANDOM.
Zamiast zawsze używać ostatniego elementu A[r] jako W wyniku wywołania RANDOM(a, b) zwracana jest liczba
rozdzielającego, będziemy używać elementu wybranego losowo z całkowita z zakresu od a do b, włącznie.
poddtablicy A[p..r].
Każda wartość jest zwracana z takim samym
Założymy przy tym, że każdy spośród r - p + 1 elementów prawdopodobieństwem.
poddtablicy może być z takim samym prawdopodobieństwem
Na przykład wynikiem wywołania RANDOM(0, 1) jest 0 z
wybrany jako element rozdzielajÄ…cy.
prawdopodobieństwem 1/2 i 1 z prawdopodobieństwem 1/2.
Taka metoda randomizowania algorytmu nazywa się Wywołanie RANDOM(3,7) zwraca którąś z wartości 3, 4, 5, 6 lub 7,
próbkowaniem losowym. każdą z prawdopodobieństwem 1/5.
Pokażemy, że średni czas działania randomizowanej wersji Każda liczba zwrócona przez RANDOM jest niezależna od liczb
algorytmu quicksort wynosi O(n log n), tak jak w przypadku zwróconych we wcześniejszych wywołaniach
przedziałów zrównoważonych.
Zmiany w procedurach PARTITION i QUICKSORT sÄ… niewielkie.
Funkcja PARTITION (przypomnienie)
W procedurze dzielącej dokonujemy zamiany dwóch elementów
przed wykonaniem podziału:
PARTITION(A, p, r)
R-PARTITION(A, p, r)
1. begin
1. begin
2. x := A[r];
2. i :=RANDOM(p, r);
3. i := p - 1;
3. zamień A[i] z A[r];
4. for j := p to r - 1 do
4. return PARTITION(A, p, r);
5. if A[j] d" x then
5. end;
6. begin
R-QUICKSORT(A, p, r)
7. i := i + 1;
1. begin
8. zamień A[i] z A[j];
2. if p < r then
9. end;
3. begin
10. zamień A[i + 1] z A[r];
4. q :=R-PARTITION(A, p, r);
11. return i + 1;
5. R-QUICKSORT(A, p, q - 1);
12. end;
6. R-QUICKSORT(A, q + 1, r);
7. end;
8. end;
Czas działania a porównania.
Naszym celem jest oszacowanie X - łącznej liczby porównań
wykonywanych we wszystkich wywołaniach PARTITION. Aby tego
Lemat 8.1
dokonać, musimy zrozumieć, kiedy algorytm porównuje dwa
Niech X będzie liczbą porównań wykonywanych w wierszu 5
elementy tablicy, a kiedy nie.
procedury PARTITION podczas całego wykonania procedury
R-QUICKSORT dla tablicy n-elementowej. Wtedy czas działania
Przemianujemy elementy tablicy A na z1, . . . , zn, gdzie zi jest
R-QUICKSORT wynosi O(n + X ).
i-tym najmniejszym elementem. Definiujemy Zij jako zbiór
elementów od zi do zj włącznie:
Dowód. W każdym wywołaniu R-PARTITION jest wybierany
element rozdzielający, który nie uczestniczy w żadnych
Zij = {zi, zi+1, . . . , zj}.
póz
niejszych wywołaniach procedur R-QUICKSORT i
Zauważmy, że każda para elementów jest porównywana co
R-PARTITION. Podczas całego wykonania algorytmu może być
najwyżej raz, bo elementy są porównywane wyłącznie z elementem
zatem co najwyżej n wywołań R-PARTITION. Jedno wywołanie
rozdzielającym, a po zakończeniu ustalonego wywołania
R-PARTITION zajmuje czas O(1) plus czas proporcjonalny do
PARTITION użyty w nim element rozdzielający już nigdy więcej
liczby iteracji pętli for w procedurze PARTITION. W każdej
nie jest porównywany z żadnym elementem.
iteracji tej pętli jest wykonywany wiersz 5, zatem liczba iteracji
pętli for jest równa liczbie porównań.
Ogólnie, po wybraniu elementu rozdzielającego x takiego, że
zi < x < zj, wiemy, że zi i zj nie będą nigdy póz
niej porównywane.
Dla przykładu załóżmy, że tablica wejściowa składa się z liczb od 1
do 10 (w dowolnej kolejności) i załóżmy, że pierwszym elementem
Z drugiej strony, jeśli zi zostanie wybrane jako element
rozdzielajÄ…cym jest 7.
rozdzielający przed wszystkimi innymi elementami Zij, to zi będzie
porównywane z każdym elementem Zij oprócz samego siebie.
Wówczas pierwsze wywołanie PARTITION rozdziela liczby na dwa
zbiory: {1, 2, 3, 4, 5, 6} i {8, 9, 10}.
Podobnie, jeśli zj zostanie wybrane jako element rozdzielający
przed wszystkimi innymi elementami Zij, to zj będzie porównywane
Podczas tej operacji 7 jest porównywane ze wszystkimi pozostałymi
z każdym elementem Zij oprócz samego siebie.
elementami, ale żadna liczba z pierwszego zbioru (np. 2) nie będzie
nigdy porównywana z żadną liczbą z drugiego zbioru (np. 9).
Z powyższych rozważań wynika, że zi i zj sa porównywane wtedy i
tylko wtedy, gdy pierwszym elementem wybranym jako
rozdzielajÄ…cy ze zbioru Zij jest zi albo zj.
Definiujemy

1 jeśli zi jest porównywane z zj
Obliczmy prawdopodobieństwo takiego zdarzenia.
Xij =
0 jeśli zi nie jest porównywane z zj.
Przed momentem, w którym pewien element zbioru Zij został
Zatem Xij jest zmienną losową przyjmującą wartość 1 z
wybrany jako rozdzielający, cały zbiór Zij wchodził w skład jednej
prawdopodobieństwem 2/(j - i + 1) albo 0 z
części podziału.
prawdopodobieństwem 1 - 2/(j - i + 1).
Każdy element zbioru Zij może zatem być z jednakowym
Ponieważ każda para elementów jest porównywana co najwyżej
prawdopodobieństwem wybrany jako pierwszy element
raz, zatem łączna liczba porównań wynosi:
rozdzielajÄ…cy.
n-1 n

X = Xij.
Ponieważ Zij ma j - i + 1 elementów, więc
i=1 j=i+1
2
Pr{zi jest porównywane z zj} = .
Liczymy wartość oczekiwaną:
j - i + 1
ëÅ‚ öÅ‚
n-1 n n-1 n n-1 n

2
íÅ‚
E(X) = E Xijłł = E(Xij) = .
j - i + 1
i=1 j=i+1 i=1 j=i+1 i=1 j=i+1
Pozostaje uzasadnić oszacowanie
StosujÄ…c zamianÄ™ zmiennych k = j - i otrzymujemy:
n

1
= O(log n).
n-1 n n-1 n-i n-1 n

k
2 2 2
k=1
E (X) = = < .
j - i + 1 k + 1 k
i=1 j=i+1 i=1 k=1 i=1 k=1
W tym celu rozdzielamy zbiór indeksów na log n przedziałów i
szacujemy sumę każdej części przez 1. Każda część składa się z
KorzystajÄ…c z oszacowania
wyrazów od 1/2i do 1/2i+1, ale bez tego ostatniego.
n

1
= O(log n),
k
n
k=1
1 1 1 1 1 1 1 1 1
= 1+ + + + + + +· · ·+ + · · · + .
k 2 3 4 5 6 7 2 log n n
(które uzasadnimy póz
niej) otrzymujemy E(X) = O(n log n).
k=1
Stąd i z Lematu 8.1 wnioskujemy, że średni (oczekiwany) czas
log n -1
log n -1
log n
działania randomizowanej wersji algorytmu quicksort dla tablicy n 2i 2i

1 1 1
d" d" = 1 d" log n + 1.
n-elementowej wynosi O(n log n).
k 2i + j 2i
k=1 i=0 j=0 i=0 j=0 i=0