Algorytmy i struktury danych

Wykład 4

Rekurencja c.d.

Temat

• Quicksort, czyli ….

• … raz jeszcze o rekurencji… lub

• … kiedy rekurencja bardzo pomaga!

Problem sortowania raz jeszcze…

Specyfikacja

Dane

n, ci

ą

g S=s

1

,…s

n

Wynik

elementy S w porz

ą

dku niemalej

ą

cymi, czyli:

s

i1

≤

s

i2

≤

…

≤

s

in

.

Dziel i zwyci

ęż

aj

1. Podziel problem na podproblemy tego

samego (lub podobnego) rozmiaru

2. Rozwi

ąż

podproblemy

3. Poł

ą

cz rozwi

ą

zania podproblemów tak,

aby uzyska

ć

rozwi

ą

zanie problemu

głównego

Sortowanie przez scalanie jako

zastosowanie zasady „dziel i rz

ą

d

ź

”

1. Podziel ci

ą

g wej

ś

ciowy S na dwa

podci

ą

gi S1, S2 (prawie) tej samej

długo

ś

ci

2. Posortuj S1 i S2 osobno (rekurencja)

3. Scal posortowane ci

ą

gi S1 i S2

Quicksort jako inny przykład

zastosowania metody dziel i zwyci

ęż

aj

1. Wybierz element s ci

ą

gu wej

ś

ciowego S i

podziel S na dwa rozł

ą

czne podzbiory:

•

S1: elementy, które s

ą

≤

s

•

S2: elementy, które s

ą

≥

s

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…

Specyfikacja

Input

l, r – liczby naturalne, a – tablica

sortowanych elementów

Output

elementy z a[l…r] w porz

ą

dku

niemalej

ą

cym, czyli

a[l]

≤

a[l+1]

≤

…

≤

a[r].

Quick sort dokładniej…

Je

ś

li l < r :

1. Wybierz x ze zbioru {a[l], a[l+1],…, a[r]} i

przemie

ść

elementy a[l], a[l+1],…, a[r] tak, aby:

•

Elementy a[l..s] s

ą

≤

x

•

Elementy a[s+1…r] s

ą

≥

x

gdzie s jest pewn

ą

liczb

ą

naturaln

ą

tak

ą

,

ż

e l

≤

s

≤

r

2. Posortuj :

•

a[l...s]

•

a[s+1…r]

Quick sort jeszcze dokładniej…

qsort

(int a[], int l, int r)

//sortuje a[l…r]

{ int s;

if (l<r) {

s = partition(a,l,r);

qsort

(a, l,

s);

qsort

(a, s+1, r);

}

}

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: idea

1.

Wybierz x

2.

i

←

l, j

←

r

3.

Dopóki i

<

j powtarzaj:

1. Zwiększaj i aż do spełnienia warunku a[i]

≥

x

2. Zmniejszaj j aż do spełnienia warunku a[j]

≤

x

Zamień a[i] z a[j]

4.

Zwróć i

Partition: implementacja

partition(int a[], int l, int r)

{ int x,y;

x=a[l];

l--;

r++;

do

{ while (a[--r]>x);

while (a[++l]<x);

if (l<r) {y=a[r]; a[r]=a[l]; a[l]=y;}

else return r;

} while (1);

}

Quick sort: zło

ż

ono

ść

pami

ę

ciowa

Pami

ęć

:

•

Tablica zawieraj

ą

ca ci

ą

g wej

ś

ciowy

•

Stała liczba dodatkowych zmiennych

•

Pami

ęć

potrzebna do realizacji

rekurencji…?

Quick sort: zło

ż

ono

ść

czasowa

•

Najgorszy przypadek: procedura partition dzieli
problem na podproblemy o rozmiarach 1 i n – 1:

T(1) = 1

T(n) = T(n-1) + T(1) + n

dla n

>

1

Rozwi

ą

zanie: T(n)

≅

n

2

/2=O(n

2

)

First recursive call

Second recursive call

Cost of partition

Quicksort: zło

ż

ono

ść

czasowa

•

„Zamierzona” sytuacja: procedura partition dzieli
problem rozmiaru n na dwa podproblemy
rozmiaru n/2:

T(1) = 1

T(n) = T(n/2) + T(n/2) + n

dla n

>

1

Rozwi

ą

zanie: T(n) = O(n log n)

Pierwsze wywoł. rek.

Koszt partition

Drugie wywoł. rek.

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)