ALG7

4.3. Duicksort, algorytm klasy Q(N log2N) 87

4.3. Quicksort, algorytm klasy 0(Nlog₂N)

Jest to słynny algorytm 1, zwany również po polsku sortowaniem szybkim. Należy on do tych rozwiązań, w których poprzez odpowiednią dekompozycję osiągnięty został znaczny zysk szybkości sortowania. Procedura sortowania dzieli się na dwie zasadnicze części: część służącą do właściwego sortowania, która nie robi w zasadzie nic robi... oprócz wywoływania samej siebie, oraz procedury rozdzielania elementów tablicy względem wartości pewnej komórki tablicy służącej za oś (ang. pivot) podziału. Proces sortowania jest dokonywany pracz tę właśnie procedurę, natomiast rekurencja zapewnia „sklejenie” wyników cząstkowych i w konsekwencji posortowanie całej tablicy.

Jak dokładnie działa procedura podziału? Otóż w pierwszym momencie odczytuje się wartość elementu osiowego P, którym zazwyczaj jest po prostu pierwszy element analizowanego fragmentu tablicy. Tenże fragment tablicy jest następnie dzielony wg klucza symbolicznie przedstawionego na rysunku 4-5.

Kolejnym etapem jest zaaplikowanie procedury Quieksort na „lewym” i „prawym” fragmencie tablicy, czego efektem będzie jej posortowanie. To wszystko!

Rys. 4 - 5.

Podział tablicy w metodzie Quicksort.

element <

•P'

element osiowy

P'

element > = 'P'

Na rysunku 4 - 6 są przedstawione symbolicznie dwa główne etapy sortowania metodąOuicksort (P oznacza tradycyjnie komórkę tablicy służącą za „oś”).

QuickSort

•P'
OuickSort r~ i		Qu\ckSon V~ ~1
< p'	p‘	>= P'

Rys. 4 - 6.

Zusuda działania procedury Quicksort.

' PatrzC.A.K. Hoare-,.Quicksorf' w Computer Journal, 5, 1(1962).

² Elementy tablicy są fizycznie przemieszczane, jeśli zachodzi potrzeba.