ALG9

4.3. Quicksort, algorytm klasy Q(N log2N) 89

•    P wartość „osiowa” (zazwyczaj będzie to tab[left]):

•    i indeks przemiatający tablicę od lefl do rij»h 1;

•    m poszukiwany indeks komórki tablicy, w której umieścimy element osiowy.

Przemiatanie tablicy służy do poukładania jej elementów w taki sposób, aby po lewej stronie ni znajdowały się wartości mniejsze od elementu osiowego, po prawej zaś — większe lub równe. W tym celu podczas przemieszczania indeksu i sprawdzamy prawdziwość niezmiennika lab[i]>P. Jeśli jest on fałszy wy, to poprzez inkrementację i wymianę wartości tabfrn] i tabfij przywracamy „porządek". Gdy zakończymy ostatecznie przeglądanie tablicy w pogoni za komórkami, które nie chciały się podporządkować niezmiennikowi, zamiana tctb[!eft] i, lab[m] doprowadzi do oczekiwanej sytuacji, przedstawionej wcześniej na rysunku 4-7.

Nic już teraz nie stoi na przeszkodzie, aby zaproponować ostateczną wersję procedury Quicksort. Omówione wcześniej etapy działania algorytmu zostały połączone w jedną procedurę:

qxorl.cpp

void qsoct(int "Łab, int left, int right)

(

if (left < right)

(

int m=left;

for (int i=left+l; icnght; i—+) if (tab[i]<tab[left;)

zamiana(tab;+-m;, tab[i]); zamiana(tab(left],tab[n]); qsort(tab,left,m-l); qsort(tab,m+l,right);

I

)

W celu dobrego zrozumienia działania algorytmu spróbujmy posortować nim „ręcznie” małą tablicę, np. zawierającą następujące liczby:

29, 40, 2, 1,6, 18. 20. 32, 23. 34. 39, 41.

Rysunek 4-8 przedstawia efekt działania tych egzemplarzy procedury Quicksort, które faktycznie coś robią.

Widać wyraźnie, że przechodząc od skrajnie lewej gałęzi drzewa do skrajnie prawej i odwiedzając w pierwszej kolejności „lewe” jego odnogi, przechadzamy się w istocie po posortowanej tablicy! W naszym programie taki spacer realizują wywołania rckurencyjne procedury qsort. Algorytm Quicksort stanowi dobry przykład techniki programowania zwanej „dziel i rządź”, która zostanie dokładniej omówiona w rozdziale 9.