Sortowanie szybkie (quicksort).
QUICKSORT(A, p, r)
1. begin
Algorytm quicksort sortuje w miejscu ciąg elementów metodą 2. if p < r then
 dziel i zwyciężaj . 3. begin
4. q :=PARTITION(A, p, r);
Dziel: Tablica A[p..r] jest dzielona (jej elementy sÄ… przestawiane)
5. QUICKSORT(A, p, q - 1);
na trzy części: A[p..q - 1], A[q] i A[q + 1..r], takie że każdy
6. QUICKSORT(A, q + 1, r);
element A[p..q - 1] jest nie większy niż A[q], który z kolei jest nie
7. end;
większy niż każdy element A[q + 1..r]. Obliczenie indeksu q
8. end;
stanowi część procedury podziału.
Jeżeli p e" r, to znaczy że tablica A[p..r] składa się z jednego
Zwyciężaj: Sortujemy podtablice A[p..q - 1] i A[q + 1..r],
elementu lub jest pusta. W takim przypadku procedura nie ma nic
używając rekurencyjnie algorytmu quicksort.
do zrobienia. Aby posortować całą n-elementową tablicę A,
Połącz: Ponieważ podtablice są sortowane w miejscu, nie
wywołujemy QUICKSORT(A, 1, n).
potrzeba nic robić, żeby połączyć rozwiązania podproblemów: cała
Funkcja PARTITION przestawia elementy tablicy A[p..r] i zwraca
tablica A[p..r] jest już posortowana.
indeks q wyznaczający podział na trzy części.
Podział tablicy - funkcja PARTITION Przykład.
Działanie PARTITION(A, 1, 8) dla A = [2, 6, 4, 8, 7, 3, 1, 5].
PARTITION(A, p, r)
x = A[8] = 5
1. begin
i j A
2. x := A[r];
0 1 [2, 6, 4, 8, 7, 3, 1, 5]
3. i := p - 1;
1 2 [2, 6, 4, 8, 7, 3, 1, 5]
4. for j := p to r - 1 do
1 3 [2, 6, 4, 8, 7, 3, 1, 5]
5. if A[j] d" x then
2 4 [2, 4, 6, 8, 7, 3, 1, 5]
6. begin
2 5 [2, 4, 6, 8, 7, 3, 1, 5]
7. i := i + 1;
2 6 [2, 4, 6, 8, 7, 3, 1, 5]
8. zamień A[i] z A[j];
3 7 [2, 4, 3, 8, 7, 6, 1, 5]
9. end;
4 8 [2, 4, 3, 1, 7, 6, 8, 5]
10. zamień A[i + 1] z A[r];
4 8 [2, 4, 3, 1, 5, 6, 8, 7]
11. return i + 1;
12. end;
q = i + 1 = 5
A[p..q - 1] = [2, 4, 3, 1], A[q] = 5, A[q + 1..r] = [6, 8, 7].
Opis działania PARTITION
Inicjowanie. Na poczÄ…tku mamy i = p - 1, j = p, zatem warunki
(1) i (2) są trywialnie spełnione. Warunek (3) jest spełniony na
Najpierw jest wybierany element x = A[r] jako element
skutek przypisania w wierszu 2.
rozdzielający, względem którego jest dokonywany podział A[p..r].
Kolejne elementy A[p..r - 1] są porównywane z x, a indeksy
Utrzymanie. Rozpatrzmy dwa przypadki. Jeśli A[j] > x, to
p, i, j, r dzielÄ… tablicÄ™ na cztery obszary:
wiersze 7 i 8 nie są wykonywane, a jedynym działaniem pętli jest
zwiększenie j o jeden. Po zwiększeniu j warunek (2) jest spełniony
[el. d" x | el. > x | el. jeszcze nie porównane z x | x].
dla k = j - 1, a wszystkie inne elementy pozostajÄ… bez zmian.
Kiedy A[j] d" x, zwiększane jest i, elementy A[i] i A[j] są
zamieniane, po czym zwiększane jest j. Po zamianie jest A[i] d" x i
Spełniony jest następujący niezmiennik pętli:
warunek (1) jest spełniony. Podobnie, mamy A[j - 1] > x,
Podczas każdego sprawdzania warunku pętli for w wierszu 4, dla
ponieważ element A[j - 1] poprzednio znajdował się na pozycji
każdego indeksu k w tablicy zachodzą zależności:
A[i + 1] czyli jest, na mocy niezmiennika, większy niż x. Polecenia
(1) Jeśli p d" k d" i, to A[k] d" x.
w wierszach 4-9 nie zmieniajÄ… elementu A[r], zatem warunek (3)
(2) Jeśli i + 1 d" k d" j - 1, to A[k] > x.
pozostaje spełniony.
(3) Jeśli k = r, to A[k] = x.
Przypadek podziałów niezrównoważonych.
Zakończenie. Na końcu mamy j = r. Na mocy niezmiennika,
Zauważmy, że gdy tablica wejściowa A[1..n] jest posortowana
podtablica A[p..i] zawiera elementy nie większe niż x,
niemalejÄ…co, to procedura PARTITION dzieli jÄ… na: A[1..n - 1],
A[i + 1..r - 1] zawiera elementy większe niż x, A[r] = x.
A[n] i ". Ponieważ wszystkie elementy zostają na swoich miejscach
W wierszu 10 element rozdzielajÄ…cy zostaje przeniesiony na swoje
(w wierszu 8 mamy i = j), podtablica A[1..n - 1] nadal jest
miejsce o indeksie i + 1 przez zamianÄ™ z pierwszym z lewej
posortowana. Działanie QUICKSORT na pustej tablicy zajmuje
elementem większym niż x. Wynik q = i + 1 zwracany przez
czas stały c0 potrzebny na sprawdzenie warunku w wierszu 2,
PARTITION spełnia teraz własność podaną w kroku  Dziel opisu
natomiast po wywołaniu rekurencyjnym QUICKSORT na
algorytmu QUICKSORT.
podtablicy A[1..n - 1] zostaje ona podzialona na A[1..n - 2],
A[n - 1] i ". I tak dalej. W ostaniem kroku podtablica A[1..2] jest
Czas działania PARTITION wynosi Ś(n), gdzie n = r - p + 1, bo
dzielona na A[1], A[2] i ".
jest (n - 1) iteracji pętli for, z których każda zajmuje czas
ograniczony przez stałą, a wszystkie operacje poza pętlą zajmują
Czas działania PARTITION dla posortowanej tablicy n-elementowej
łącznie stały czas.
wynosi a(n - 1) + b, gdzie stała a oznacza czas jednej iteracji pętli
for (wiersze 4-9), a b jest czasem spędzonym poza pętlą.
Dowód. Niech T (n) oznacza pesymistyczny czas działania
A
ączny czas T (n) działania algorytmu QUICKSORT dla tablicy
QUICKSORT dla tablicy rozmiaru n. Wtedy T (0) = T (1) = c0, a
posortowanej spełnia zależność rekurencyjną:
dla n e" 2 mamy
T (1) = c0,
T (n) = a(n - 1) + b + T (n - 1) + c0, dla n e" 2. T (n) d" a(n - 1) + b + maxq(T (q - 1) + T (n - q)),
Prawą stronę drugiego równania możemy rozwinąć w sumę
gdzie maksimum bierzemy po wszystkich możliwych wartościach
q " {1, . . . , n}.
n

T (n) = a (i - 1) + b(n - 1) + c0n,
Pokażemy przez indukcję, że T (n) d" cn2 + c0 dla pewnej stałej
i=2
c > 0. Dla n = 0, 1 nierówność jest spełniona. Załóżmy, że jest
a(n - 1)(n - 2)
ona spełniona dla każdej liczby naturalnej mniejszej niż n, gdzie
T (n) = + b(n - 1) + c0n = Åš(n2).
2
n e" 2. Korzystając z równania rekurencyjnego i założenia
Pokażemy, że opisany przypadek podziałów niezrównoważonych
indukcyjnego mamy:
jest przypadkiem najgorszym:
Lemat 7.1
T (n) d" a(n - 1) + b + maxq(c(q - 1)2 + c(n - q)2 + 2c0)
Czas działania algorytmu quicksort dla dowolnej tablicy rozmiaru n
wynosi O(n2).
= a(n - 1) + b + c · maxq((q - 1)2 + (n - q)2) + 2c0.
Przypadek podziałów zrównoważonych.
Wyrażenie (q - 1)2 + (n - q)2 przyjmuje największą wartość w
przedziale zmienności parametru 1 d" q d" n na jednym z końców
Przy najrówniejszym możliwym podziale w wyniku wykonania
tego przedziału, bo współczynnik przy q2 jest dodatni, zatem
procedury PARTITION otrzymujemy dwie poddtablice o
parabola nie ma maximum. StÄ…d
rozmiarach n/2 i n/2 - 1. Zakładając, że każde wywołanie
procedury PARTITION daje taki zrównoważony podział,
maxq((q - 1)2 + (n - q)2) d" (n - 1)2,
otrzymujemy równanie rekurencyjne na czas działania algorytmu
quicksort:
T (n) d" a(n - 1) + b + c(n - 1)2 + 2c0.
Dla zakończenia dowodu wystarczy dobrać stałą c tak, żeby dla
T (n) = T ( n/2 ) + T ( n/2 - 1) + Åš(n).
każdego n było
Równanie to jest podobne do równania określającego
a(n - 1) + b + c(n - 1)2 + 2c0 d" cn2 + c0,
pesymistyczny czas działania algorytmu mergesort. Analogicznie
można udowodnić, że T (n) = O(n log n).
a(n - 1) + b + c0 d" c(2n - 1) = c(n - 1) + cn,
Zatem w przypadku podziałów zrównoważonych quicksort działa
a to jest spełnione dla c e" max{a, b + c0}.
znacznie szybciej niż w przypadku pesymistycznym.