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.
Wyszukiwarka
Podobne podstrony:
ALG7 4.3. Duicksort, algorytm klasy Q(N log2N) 874.3. Quicksort, algorytm klasy 0(Nlog2N) Jest to s
ALG9 1.1. Jak to wcześniej bywało, czyli... 19 • jest skończony (wynik algorytmu musi zostać „kiedy
ALG3 4.1. Sortowanie przez wstawianie, algorytm klasy 0(N2) 83 Idea tego algorytmu opiera się na na
ALG5 4.2. Sortowanie bąbelkowe, algorytm klasy 0(H2) 85 for (int j-n-l;j>i;j—) if (tab[j]<tab
ALG9 5.1. Listy jednokierunkowe 119 wartość zwracaną przez funkcję: w normalnej sytuacji winien to
ALG 2 272 Rozdziału. Algorytmy numei 272 Rozdziału. Algorytmy numei (czyli F(z)) //zwraca wartość fu
IMG89 (3) ■ wartość skuteczna sygnału pomiarowego Wartość napięcia skutecznego sygnału zmiennego je
Algorytm Euklidesa — specyfikacja Stan Wartościowanie zmiennych M, N i wynik Prewarunek M> 0, N&g
Podział na klasy równoważności (9) zależności i wartości nieprawidłowe •
petle2 4 Wg algorytmu Hornera liczone są wartości wielomianu przez konimter • Wielomian
dsc00288 (7) Przykład (alg. B. 7*3)o._: A 0000 ot ooi r 5-r 7 j» ni ^ 0111 Wartości
ALG4 84Rozdział 4. Algorytmy sortowania insert.cpp void InsertSort (int *tab) foriint i=l; i<n;i
więcej podobnych podstron