Temat

• 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)