• Quicksort, czyli ….
• … raz jeszcze o rekurencji… lub
Algorytmy i struktury danych
• … kiedy rekurencja bardzo pomaga!
Wykład 4
Rekurencja c.d.
Problem sortowania raz jeszcze…
Dziel i zwyciężaj
1. Podziel problem na podproblemy tego Specyfikacja
samego (lub podobnego) rozmiaru
Dane
2. Rozwiąż podproblemy
n, ciąg S=s ,…s
1
n
3. Połącz rozwiązania podproblemów tak, Wynik
aby uzyskać rozwiązanie problemu
elementy S w porządku niemalejącymi, czyli: głównego
s ≤ s ≤ … ≤ s .
i1
i2
in
Sortowanie przez scalanie jako Quicksort jako inny przykład
zastosowanie zasady „dziel i rządź”
zastosowania metody dziel i zwyciężaj 1. Podziel ciąg wejściowy S na dwa
1. Wybierz element s ciągu wejściowego S i podciągi S1, S2 (prawie) tej samej
podziel S na dwa rozłączne podzbiory:
długości
•
S1: elementy, które są ≤ s
2. Posortuj S1 i S2 osobno (rekurencja)
•
S2: elementy, które są ≥ s
3. Scal posortowane ciągi S1 i S2
2. Posortuj S1 i S2 osobno (rekurencja) 3. Zwróć złączone ciągi S1 i S2
Uwaga
Różne wystąpienia elementu s mogą należeć do S1 lub S1, ALE
każda kopia należy tylko do jednego ze zbiorów S1, S2.
Sortowanie dokładniej…
Quick sort dokładniej…
Specyfikacja
Jeśli l < r :
Input
1. Wybierz x ze zbioru { a[ l], a[ l+1],…, a[ r]} i przemieść elementy a[ l], a[ l+1],…, a[ r] tak, aby: l, r – liczby naturalne, a – tablica
•
Elementy a[ l.. s] są ≤x sortowanych elementów
•
Elementy a[ s+1… r] są ≥x Output
gdzie s jest pewną liczbą naturalną taką, że l≤ s≤ r elementy z a[ l… r] w porządku 2. Posortuj :
niemalejącym, czyli
•
a[ l... s]
•
a[ s+1… r]
a[ l] ≤ a[ l+1] ≤ … ≤ a[ r].
Quick sort jeszcze dokładniej…
Partition: idea
qsort(int a[], int l, int r) 1.
Wybierz x
//sortuje a[l…r]
2.
i ← l, j ← r
{ int s;
if (l<r) {
3.
Dopóki i < j powtarzaj: s = partition(a,l,r);
1. Zwiększaj i aż do spełnienia warunku a[ i] ≥ x qsort(a, l,
s);
qsort(a, s+1, r);
2. Zmniejszaj j aż do spełnienia warunku a[ j] ≤ x
}
Zamień a[ i] z a[ j]
}
4.
Zwróć i
int partition(int a[], int l, int r):
•
Wybierz x z podtablicy a[ l.. r]
•
Poprzemieszczaj elementy tak, aby:
–
Elementy w a[ l.. j] są ≤ x
–
Elementy w a[ j+1.. r] są ≥ x
•
Zwróć j jako wynik
Partition: implementacja
Quick sort: złożoność pamięciowa
partition(int a[], int l, int r)
{ int x,y;
Pamięć:
x=a[l];
l--;
•
Tablica zawierająca ciąg wejściowy
r++;
•
Stała liczba dodatkowych zmiennych
do
{ while (a[--r]>x);
•
Pamięć potrzebna do realizacji
while (a[++l]<x);
rekurencji…?
if (l<r) {y=a[r]; a[r]=a[l]; a[l]=y;}
else return r;
} while (1);
}
Quick sort: złożoność czasowa Quicksort: złożoność czasowa
•
Najgorszy przypadek: procedura partition dzieli
•
„Zamierzona” sytuacja: procedura partition dzieli problem na podproblemy o rozmiarach 1 i n – 1: problem rozmiaru n na dwa podproblemy
T(1) = 1
rozmiaru n/2:
T(n) = T(n-1) + T(1) + n
dla n > 1
T(1) = 1
T(n) = T(n/2) + T(n/2) + n
dla n>1
First recursive call
Second recursive call
Cost of partition
Pierwsze wywoł. rek.
Drugie wywoł. rek.
Koszt partition
Rozwiązanie: T( n) ≅ n 2/2=O( n 2) Rozwiązanie: T( n) = O( n log n) Quicksort: złożoność czasowa
W praktyce: quicksort jest najszybszym algorytmem sortowania.
Pyt.:
Jaki czas preferujesz n 2 czy n log n?
Uwagi:
•
Możliwe jest uzyskanie czasu O(n log n) w najgorszym przypadku (korzystamy z algorytmu liniowego szukającego mediany)
•
Wiadomo, że średni czas działania Quicksort jest O( n log n)