Algorytmy i struktury danych

Wykład 4

Rekurencja c.d.

Temat wykładu

• Rekurencja/metoda dziel i zwyci

ęż

aj

• Sortowanie przez scalanie

Scalanie ci

ą

gów posortowanych

Dane

n, m, a

1

,

…

,a

n

, b

1

,

…

,b

m

takie,

ż

e

a

1

≤…≤

a

n

oraz

b

1

≤…≤

b

m

Wynik

c

1

≤…≤

c

n+m

gdzie {

c

1

…

c

n+m

} to suma

(wielo)zbiorów {

a

1

,

…

, a

n

} oraz {

b

1

,

…

,b

m

}

Scalanie – przykład

Przykład:

Dane

7 5

3 5 5 7 8 8 9

3 4 6 12 14

n m

a

1

,

…

,a

n

b

1

,

…

,b

m

Wynik

3

3 4

5 5

6

7 8 8 9

12 14

Scalanie

Algorytm
1. i

←

1, j

←

1, k

←

1

2. While (i

≤

n) and (j

≤

m) do

1. If a

i

≤

b

j

then

•

c

k

←

a

i,

i

←

i+1

else

•

c

k

←

b

j,

j

←

j+1

2. k

←

k+1

3. If i

≤

n: kopiuj a

i

,…,a

n

do c

k

,…,c

n+m

else kopiuj b

j

,…,b

m

do c

k

,…, c

n+m

Scalanie – inna specyfikacja

Dane
•

Tablica

int t[]

•

Liczby l1, l2, r2

takie

ż

e

•

t[l1..l2-1]

posortowane (odpowiada a)

•

t[l2..r2]

posortowane (odpowiada b)

Wynik

t[l1..r2]

posortowane (zawiera sum

ę

a i b)

l1

l2

r2

Scalanie – inna specyfikacja

Algorytm
1. i

←

l1

, j

←

l2

, k

←

1, r1

←

l2-1

2. while (i

≤

r1) and (j

≤

r2) do

1. If t[ i ]

≤

t[ j ] then

•

c[ k ]

←

t[ i ],

,

i

←

i+1

else

•

c[ k ]

←

t[ j ],

,

j

←

j+1

2. k

←

k+1

3. If i

≤

n: kopiuj t[i],…,t[r1] do c[k],…,c[r2-l1+1]

else kopiuj t[j],…,t[r2] do c[k],…,c[r2-l1+1]

4. Kopiuj c[1..r2-l1+1] do t[l1..r2]

Scalanie – inna specyfikacja

Implementacja

merge(int t[], int l1, int l2, int r2)

{ int k,i,j,c[n],bg, r1;

bg=l1;

k=0;

r1=l2; r2++;

while (l1<r1 && l2<r2)

if (t[l1]<t[l2]) { c[k]=t[l1]; k++; l1++; }

else

{ c[k]=t[l2]; k++; l2++; }

while (l1<r1)

{ c[k]=t[l1]; k++; l1++; }

while (l2<r2)

{ c[k]=t[l2]; k++; l2++; }

k=0;

for (j=bg; j<r2; j++)

t[j]=c[k++];

}

Scalanie – inna specyfikacja

Bardziej wydajna implementacja

merge(int t[], int l1, int l2, int r2)

{ int k,i,j,c[n],bg, r1;

bg=l1;

k=0;

r1=l2; r2++;

while (l1<r1 && l2<r2)

c[k++]=(t[l1]<t[l2])? t[l1++]:t[l2++];

while (l1<r1)

c[k++]=t[l1++];

while (l2<r2)

c[k++]=t[l2++];

while (k>=0) t[--r2]=c[--k];

}

Alg. scalania - zło

ż

ono

ść

Rozmiar danych: n + m

Pami

ęć

: n+m

Czas

: O(n+m)

Scalanie – poprawno

ść

Niezmiennik p

ę

tli:

•

c[0..k-1] = t[l1..i-1]

∪

t[l2..j-1]

•

c[0]

≤

...

≤

c[k-1]

Sortowanie przez scalanie

Specyfikacja

Dane: n, a[0..n – 1]

Wynik: elementy a[0.. n – 1] w porz

ą

dku

niemalej

ą

cym, czyli

a[0]

≤

a[1]

≤

…

≤

a[n – 1].

Sortowanie przez scalanie

Algorytm (idea):
•

Je

ś

li n=1: zwró

ć

tablic

ę

a

•

Podziel a[0..n-1] na podtablice a[0..k],
a[k+1..n-1] o równej długo

ś

ci

•

Posortuj a[0..k]

//rekurencja!

•

Posortuj a[k+1..n-1]

//rekurencja!

•

Scal a[0..k] oraz a[k+1..n-1]

•

Zwró

ć

a jako wynik

Sortowanie przez scalanie

Implementacja:

mergesort

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

//sortuje a[l..r]

{ int s,j,k;

if (r-l>0)

{ s=(l+r)/2;

mergesort

(a,l,s+1);

mergesort

(a,s+1,r);

merge(a,l,s+1,r);

}

}

Sortowanie przez scalanie

Drzewo wywoła

ń

ms(a, 0, 19)

ms(a, 0, 9)

ms(a, 10, 19)

ms(a, 0, 4)

ms(a, 5, 9)

ms(a,10,14)

ms(a, 15, 19)

(0, 2)

(3, 4)

(5, 7)

(8,9)

(10,12)

(13,14)

(15,17)

(18,19)

(0,1)

(2, 2)

(5,6)

(7, 7)

(0,1)

(2, 2)

(15,16)

(17,17)

Uwaga: wywołania dla niektórych ci

ą

gów o długo

ś

ci

≤

2 nie zostały narysowane.

Sortowanie przez scalanie - zło

ż

ono

ść

Pami

ęć

(n = r – l + 1)

•

n+O(1) –pami

ęć

potrzebna przy scalaniu

•

Pami

ęć

do realizacji rekurencji… ?

Czas: (n = r – l + 1)

•

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

Rozwi

ą

zanie: T(n)

≅

n log n

pierwsze wywoł. rek.

koszt scalania

drugie wywoł. rek.