Idea algorytmu szybkiego sortowania pochodzi od C.A.R.Hoare i polega na zastosowaniu zasady "dziel i zwyciężaj": podzielmy zadanie sortownia ciągu n elementowego na dwa podzadania o mniej więcej takich samych rozmiarach, a uzyskane wyniki połączmy w jeden uporządkowany ciąg. Aby połączenie posortowanych odcinków nie wymagało dodatkowej pracy (dodatkowych porównań), wystarczy aby elementy jednego posortowanego odcinka były nie większe od elementów drugiego posortowanego odcinka. 

Metoda

1. Rozdzielić elementy danego ciągu e względem pewnego wybranego elementu v, na elementy mniejsze od v i elementy większe od v.
2. Umieścić v na właściwej pozycji, którą ten element powinien zajmować w ciągu uporządkowanym.
3. Posortować (stosując tę samą metodę) elementy mniejsze od v.
4. Posortować (stosując tę samą metodę) elementy większe od v.

Rozdzielanie ciągu omawialiśmy przy okazji innego algorytmu stosującego zasadę "dziel i zwyciężaj, a mianowicie algorytmu Hoare wyszukiwania  k-tego co do wielkości elementu ciągu (por. wykład III, p.6). Podany tam algorytm Partition zastosujemy teraz w procesie sortowania.

Przykład 3.1

Niech ciąg e składa się z następujących elementów: 7,2,4,5,1,6,3,5,9,8,0. Kolejne kroki algorytmu przedstawiliśmy w tabeli. Elementy, względem których rozdzielany był ciąg, są zaznaczone kolorem czerwonym, elementy młodsze w rozważanym podziale - kolorem żółtym, a starsze - kolorem zielonym.

W pierwszym kroku rozdzielamy dany ciąg względem elementu e[11]. Ponieważ 0 jest mniejsze od wszystkich elementów ciągu, więc zbiór elementów "młodszych" jest w tym przypadku pusty. Zbiór elementów "starszych" to ciąg 2,4,5,1,3,6,5,8,9,7. Rozdzielamy go względem 7. Część "starsza" zawiera elementy 9,8, a "młodsza" elementy 2,4,5,1,3,6,5. Zajmiemy się najpierw posortowaniem części "młodszej". Zastosowanie Partition do ciągu 2,4,5,1,3,6,5 rozdzieli go na ciąg 2,4,5,1,3 oraz ciąg jednoelementowy 6, który  jest już uporządkowany. Ciąg 2,4,5,1,3 rozdzielony względem 3 utworzy dwa podzbiory {1,2} i {4,5}. Pozostało już tylko sprawdzenie kolejności w parach na pozycjach 2-3, 5-6, 10-11. J

Uwaga Algorytm Partition nie jest jedynym dobrym sposobem rozdzielania elementów zbioru skończonego. W prezentacji dołączonej do wykładu znajduje się opis innego algorytmu rozdzielania Split. W dalszej części wykładu poznamy jeszcze inny sposób, wykorzystujący bardziej zaawansowane struktury danych.

Przedstawiany w tym punkcie algorytm QuickSort jest procedurą rekurencyjną o dwóch parametrach formalnych l i p, które oznaczają lewy i prawy indeks rozważanego ciągu. Jak zwykle zakładamy, że elementy sortowanego ciągu zostały umieszczone w tablicy e[1],...e[n].

Analiza poprawności

Jeżeli ciąg składa się z jednego tylko elementu (tzn. l = r), to oczywiście jest ciągiem uporządkowanym. Załóżmy, że algorytm QuickSort zastosowany do dowolnego ciągu krótszego niż p-l+1 ustawia jego elementy w porządku niemalejącym. Dokładniej, zakładamy, że o ile j-i < p-l, to w wyniku wywołania QuickSort(i,j) mamy  e[i] £ e[i+1] £... £ e[j], oraz elementy e[i],...,e[j] są permutacją oryginalnych danych na pozycjach od i-tej do j-tej.

Na mocy twierdzenia o poprawności algorytmu Partition (por. twierdzenie III.6.1), po wykonaniu instrukcji  "Partition(l,p);"

{e[l],..., e[x-1]} £ e[x] £ {e[x+1],..., e[p]}.

Wiemy ponadto, że l £ x £ p. Wynika stąd, że  (x-1) - l < p - l oraz  p - (x+1)< p - l, co umożliwia nam zastosowanie założenia indukcyjnego do rekurencyjnych wywołań "QuickSort(l, x-1);" i  "QuickSort(x+1, p);". W wyniku pierwszego wywołania otrzymamy e[l] £ e[l+1] £... £ e[x-1], a w wyniku drugiego wywołania  e[x+1] £ e[x+2] £ ... £ e[p].  Ostatecznie cały fragment od l do p jest ciągiem uporządkowanym. Na mocy zasady indukcji wnioskujemy, że dla dowolnego n,  wykonanie algorytmu QuickSort(1,n)  spowoduje uporządkowanie ciągu e[1],...,e[n].

Zauważmy, tak jak w przypadku poprzednio omawianych algorytmów, że ani typy ani wartości elementów nie mają w tym algorytmie znaczenia. Algorytm działa poprawnie, tzn. ustawia elementy ciągu w porządku niemalejącym, w dowolnej strukturze danych, na elementach której określony jest liniowy porządek.

Analiza kosztu.

Rozważmy najpierw przypadki szczególne. Jak zachowa się algorytm QuickSort dla ciągu e uporządkowanego niemalejąco?   Algorytm Partition używa do rozdzielania, elementu z pozycji ostatniej, czyli w tym przypadku największego. Zatem w wyniku rozdzielenia ciągu n elementowego zbiór elementów większych od rozdzielającego będzie pusty, a zbiór elementów mniejszych będzie zawierał n-1 elementów. Wykonany przy tym n-1 porównań. Podobnie będzie w każdym następnym wykonaniu Partition. Jest to więc najgorszy przypadek dla tego algorytmu.  Liczbę wykonanych porównań możemy opisać równaniem  W(n) = (n-1) + W(n-1), którego rozwiązaniem jest funkcja W(n) = n(n-1)/2  rzędu  Q(n²).

Aby policzyć koszt średni, załóżmy, że wszystkie permutacje elementów danego ciągu są tak samo prawdopodobne i że każdy podział ciągu w wyniku działania algorytmu Partition jest tak samo prawdopodobny. Ponieważ pozycja rozdzielająca może się znajdować na dowolnym z n miejsc, więc przyjmujemy, że  P( pozycja elementu rozdzielającego = x) = 1/n dla dowolnego x=1,...,n.  Koszt pierwszego wykonania Partition wynosi n-1 porównań. Jeżeli element rozdzielający znajdzie się na pozycji x, to kolejne wywołania rekurencyjne dotyczą ciągu x-1 elementowego i n-x elementowego. Mamy więc następujące równanie rekurencyjne dla średniego kosztu algorytmu:

A(1) = 0, A(n) = (n-1) + (1/n) S _x=1,...,n (A(x-1) + A(n-x)).

Po uproszczeniu, równanie przyjmuje postać

A(n) = (n-1) +(2/n) S _x=1,...,n-1 A(x),

a jego rozwiązaniem jest funkcja A(n)= c n lg n. Koszt średni algorytmu QuickSort jest więc liniowo-logarytmiczny.

Pytanie 3:  Ile porównań wykona algorytm QuickSort dla ciągu dziesięcioelementowego odwrotnie uporządkowanego?
 

« poprzedni punkt

następny punkt »