1 przedstawiającego randomizujący kod Quicksort, aby drogą analizy sprawdzał średnią liczbę porównań potrzebnych do posortowania tablicy zawierającej unikatowe elementy. Spróbujemy też uzyskać jak najwięcej przy użyciu jak naj-mniejszej ilości kodu, czasu i miejsca.
Aby określić średnią liczbę porównań, najpierw rozszerzymy funkcjonalność programu o możli-wość ich zliczania. W tym celu inkrementujemy zmienną comps przed porównaniem w wewnętrznej pętli (listing 3.2).
2 J. Bentley, M. D. McIlroy, Engineering a sort function, „Software-Practice and Experience”, Vol. 23, No. 11 — przyp. red.
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
4 9
L I S T I N G 3 . 2 . Wewnętrzna pętla algorytmu Quicksort przystosowana do zliczania porównań for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
Jeśli uruchomimy program tylko dla jednego n, dowiemy się, ile porównań to jedno uruchomienie potrzebuje. Jeśli powtórzymy tę operację wielokrotnie dla wielu wartości n i przeprowadzimy statystyczną analizę wyników, uzyskamy wartość średnią. Algorytm Quicksort potrzebuje około 1,4 n × l g ( n ) porównań do posortowania n elementów.
Nie jest to wcale zły sposób na uzyskanie wglądu w działanie programu. Dzięki 13 wierszom kodu i kilku eksperymentom można sporo odkryć. Znane powiedzenie przypisywane pisarzom takim jak Blaise Pascal i T. S. Eliot brzmi: „Gdybym miał więcej czasu, napisałbym Ci krótszy list”. My mamy czas, więc poeksperymentujemy trochę z kodem, aby napisać krótszy (i lepszy) program.
Zagramy w przyspieszanie eksperymentu, próbując zwiększyć statystyczną dokładność i wgląd w dzia-
łanie programu. Jako że wewnętrzna pętla wykonuje dokładnie u-l porównań, możemy nieco przy-spieszyć działanie programu, zliczając te porównania za pomocą pojedynczej operacji poza pętlą.
Po tej zmianie algorytm Quicksort wygląda jak na listingu 3.3.
L I S T I N G 3 . 3 . Algorytm Quicksort po przeniesieniu inkrementacji na zewnątrz pętli comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
Program ten sortuje tablicę i jednocześnie sprawdza liczbę potrzebnych porównań. Jeśli jednak na-szym celem jest tylko zliczenie porównań, nie musimy sortować tablicy. Na listingu 3.4 zostało usunięte prawdziwe sortowanie i pozostał tylko szkielet różnych wywołań wykonywanych przez program.
L I S T I N G 3 . 4 . Szkielet algorytmu Quicksort zredukowany do zliczania void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
Program ten działa dzięki losowemu wybieraniu przez Quicksort elementu dzielącego i dzięki za-
łożeniu, że wszystkie elementy są unikatowe. Jest on wykonywany w czasie proporcjonalnym do n.
Podczas gdy program z listingu 3.3 wymagał proporcjonalnej do n ilości miejsca, teraz została ona zredukowana do stosu rekurencji, który średnio jest proporcjonalny do l g ( n ) .
5 0
R O Z D Z I A Ł 3 .
Mimo że indeksy (l i u) tablicy są niezbędne w prawdziwym programie, w tej wersji szkieletu nie mają znaczenia. Można je zastąpić jedną liczbą całkowitą (n), która będzie określała rozmiar podtablicy do posortowania (listing 3.5).
L I S T I N G 3 . 5 . Szkielet algorytmu Quicksort z jednym argumentem określającym rozmiar void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
Bardziej naturalne teraz będzie przetworzenie tej procedury do postaci funkcji zliczającej porównania (ang. comparison count — cc), która zwraca liczbę porównań użytych przez jedno wykona-nie algorytmu Quicksort. Funkcję tę przedstawia listing 3.6.
L I S T I N G 3 . 6 . Szkielet algorytmu Quicksort zaimplementowany jako funkcja int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
Przykłady zamieszczone na listingach 3.4, 3.5 i 3.6 rozwiązują ten sam podstawowy problem i potrzebują na to tyle samo czasu i pamięci. Każda kolejna wersja ma poprawioną formę, dzięki czemu jest nieco bardziej przejrzysta i zwięzła od poprzedniej.
Definiując paradoks wynalazcy (ang. inventor’s paradox), George Pólya oznajmia, że: „Bardziej ambitny plan może mieć więcej szans na powodzenie”3. Spróbujemy teraz wykorzystać ten paradoks w analizie Quicksort. Do tej pory zadawaliśmy sobie pytanie, ile porównań potrzebuje algorytm Quicksort do posortowania tablicy zawierającej n elementów. Teraz zadamy bardziej ambitne pytanie: ile średnio porównań potrzebuje algorytm Quicksort do posortowania losowej tablicy o rozmiarze n? Możemy rozszerzyć kod z listingu 3.6, aby uzyskać pseudokod widoczny na listingu 3.7.
L I S T I N G 3 . 7 . Średnia liczba porównań algorytmu Quicksort jako pseudokod float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
Jeśli dane wejściowe zawierają maksymalnie jeden element, Quicksort nie wykonuje żadnych porów-nań, jak w przykładzie z listingu 3.6. W przypadku n o większej wartości kod ten bierze pod uwagę każ-
dą wartość dzielącą (od pierwszego do ostatniego elementu — każdy jest równie prawdopodobny) 3 George Pólya, How to solve it, Princeton University Press, 1945 — przyp. red.
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
5 1