1

Algorytmy i struktury danych

wykład 4

Algorytmy sortowania cz.2

2/38

Plan prezentacji



sortowanie metodą drzewa



sortowanie metodą kopcowania (Heapsort)



sortowanie metodą scalania



porównanie poznanych metod sortowania



wyszukiwanie wskazanego elementu tablicy

3/38

Poznane metody sortowania



przez wstawianie



przez wybieranie



bąbelkowe



przez wstrząsanie (shakesort)



szybkie (quicksort)

4/38

Sortowanie drzewiaste



buduje się drzewo wyboru, składające się elementów
sortowanej tablicy znajdujących się na najniższym
poziomie (gałęziach) drzewa



porównując wielokrotnie dwa elementy wyszukany
zostanie najmniejszy element (korzeń drzewa)



eliminuje się element z korzenia i ponownie metodą
porównań wyznacza najmniejszy, większy od
poprzedniego korzenia

5/38

Sortowanie drzewiaste – budowa

drzewa

5

4

8

1

9

10

2

7

2

4

1

9

2

1

1

6/38

Sortowanie drzewiaste – usunięcie
korzenia- elementu najmniejszego

5

4

8

-

9

10

2

7

2

4

-

9

2

-

-

7/38

Sortowanie drzewiaste – wybór nowego
korzenia- elementu najmniejszego

5

4

8

-

9

10

2

7

2

4

8

9

2

8

2

8/38

Sortowanie drzewiaste – analiza



po n krokach drzewo jest puste → tablica
posortowana



liczba porównań Pr=log

2

n



cały proces sortowania wymaga n

∙

logn

operacji prostych oraz n operacji
budowania drzewa

9/38

Sortowanie przez kopcowanie

(heap sort)



jest ulepszoną wersją sortowania
drzewiastego



opiera się na pojęciu kopca

10/38

Kopiec (heap) - definicja

ci

ąg elementów h

l

, h

l+1

,…,h

p

spe

łniających zależności:

h

i

≥ h

2i

, h

i

≥

h

2i+1

dla ka

żdego i = l…p/2

h10

h11

h12

h9

h8

h4

h5

h6

h7

h2

h3

h1

h

1

=max(h

l

,…,h

n

)

11/38

Kopiec (heap) - w

łaściwości



tablica reprezentowana jest w postaci kopca (drzewa
binarnego)



kopiec budowany jest od góry



kopiec jest zape

łniony na każdym poziomie, wyjątkiem

jest najni

ższy poziom, zapełniany od lewej strony



ka

żdy węzeł drzewa odpowiada jednemu elementowi

tablicy



dany w

ęzeł dla węzłów poniższych jest ojcem



w

ęzły poniżej ojca (i) → lewy syn (2∙i) i prawy syn

(2∙i+1)



własność kopca: h[ojciec(i)] ≥ h[i] dla każdego węzła
i nie będącego korzeniem

12/38

Zamiana listy na kopiec

Elementy listy: 7,2,6,4,8,1,9,10,3,5

5

3

10

4

8

1

9

2

6

7

13/38

Przywracanie własności kopca



procedura wywoływana gdy jeden z elementów
kopca nie spełnia zależności h[ojciec(i)]

≥

h[i]



polega na przesunięciu elementu na niższe poziomy
drzewa (kopca) w ten sposób, aby poddrzewo
zaczepione w danym węźle było kopcem



jeżeli obaj synowie mają większą wartość, to element
sprawdzany zamieniany jest z większym synem



jeżeli tylko jeden syn ma większą wartość, to z nim
następuje zamiana

14/38

Budowa kopca

5

3

4

10

8

1

9

2

6

7

5

3

4

10

8

1

6

2

9

7

1

2

15/38

Budowa kopca

5

3

2

4

8

1

6

10

9

7

5

3

2

4

7

1

6

8

9

10

3

4

16/38

Sortowanie danych



sortowaniu podlega tablica T(1..n) reprezentowana przez

zbudowany z jej elementów kopiec o n węzłach



element o największej wartości znajduje się zawsze w

danym kroku sortowania (po przywróceniu właściwości

kopca) w korzeniu (na górze kopca)



element z korzenia h(1) zostaje w danym kroku sortowania

zamieniony w drzewie/kopcu z elementem o największym

indeksie h(n)



węzeł n zostaje usunięty z kopca, dalszemu sortowaniu

podlega tablica T(1..n-1) reprezentowana przez kopiec o

elementach h(1)-h(n-1)



sprawdza się, czy zachowana jest własność kopca i

ewentualnie wykonuje się procedurę jej przywracania

17/38

Sortowanie danych – 1. krok

5

3

2

4

7

1

6

8

9

10

10

3

2

4

7

1

6

8

9

5

zamiana elementu

największego i

ostatniego

przywracanie

właściwości kopca

18/38

Sortowanie danych – 2. krok

1

2

10

3

2

4

7

1

5

8

6

9

10

9

2

4

3

1

5

7

6

8

19/38

Sortowanie danych 3. i 4. krok

3

4

10

9

8

2

3

1

5

4

6

7

10

9

8

2

3

1

7

4

5

6

20/38

Sortowanie danych – ostatni krok

9

10

9

8

4

5

6

7

2

3

1

1

2

3

4

5

6

7

8

9

10

21/38

Budowa kopca - procedura

void budowa_kopca(int t[], int r)

{

int wtemp;

for(int k=r/2;k>0;k--)

//indeks ostatniego węzła-ojca

przywracanie_kopca(t,k,r);

do

//rozpoczęcie sortowania poprzez wymiany elementów

{

wtemp=t[0];

t[0]=t[r-1]; t[r-1]=wtemp;

//zamiana największy-ostatni

r--;

// pominięcie (odłączenie) największego elementu

przywracanie_kopca(t,1,r);

//po zamianie najw.-ostatni

} while (r>1);

// r=1 to posortowana cała tablica

}

22/38

Przywracanie własności kopca –
procedura

void przywracanie_kopca(int t[], int k, int r)

{

int j;

int wtemp=t[k-1];

// zapamiętanie sprawdzanego węzła-ojca

while(k<=r/2)

{

j=2*k;

// nr 1. syna dla ojca o nr=k

if(j<r && t[j-1]<t[j]) j++;

//wybranie większego z synów

if(wtemp>=t[j-1]) break;

//ojciec>=syn, więc nie ma zamiany

else

//ojciec<syn, więc jest zamiana

{

t[k-1]=t[j-1];

//zamiana ojca z większym synem

k=j;

//ster. do węzła większego syna aby spr. z jego nowymi synami

}

}

t[k-1]=wtemp;

//ostateczna pozycja ojca

}

23/38

Sortowanie przez kopcowanie - przykład

budowa

kopca

posortowana

część tablicy

24/38

Sortowanie przez kopcowanie -
analiza



zalecane do sortowania dużych tablic



im większa tablica, tym większa efektywność
metody



w najgorszym przypadku wymaga n

∙

logn operacji

podstawowych



średnia liczba przesunięć wynosi 0.5

∙

n

∙

logn



metoda jest wrażliwa na początkowe ułożenie
elementów (zwłaszcza w kolejności odwrotnej)

25/38

Sortowanie przez scalanie



podobna do quicksort



jest metodą rekurencyjną typu „dziel i zwyciężaj”



schemat działania:



podział tablicy n-elementowej na dwie podtablice zawierające
po n1=n/2 oraz n2=n-n1 elementów



sortowanie metodą przez scalanie każdej podtablicy



łączenie posortowanych podtablic w jedną tablicę



tablica dzielona jest aż do pojedynczych elementów
(wówczas p=k)

26/38

Sortowanie przez scalanie

void sort_scalanie(int t[], int p, int k)

{

int m;

if(p<k)

{

m=(p+k)/2;

sort_scalanie(t,p,m);

sort_scalanie(t,m+1,k);

scalanie(t,n,p,m,k);

}

}

podzia

ł na dwie podtablice

wywo

łania rekurencyjne

scalenie podtablic

27/38

Scalanie - opis



wykonywane jest dla podtablic uzyskanych w
procesie dzielenia, w odwrotnej kolejności



scalanie podtablic t1:{x

p

..x

m

} oraz

t2{x

m+1

..x

k

} do tablicy t:{x

p

..x

k

} odbywa się

następująco



i= x

p

..x

m

, j=x

m+1

..x

k



jeżeli t1[i]<=t2[j], wstawianie t1[i] do t; i:=i+1



jeżeli t2[j]<t1[i], wstawianie t2[j] do t; j:=j+1

28/38

Scalanie - procedura

void scalanie( int t[], int r, int p,

int m, int k)

{

int* t2=new int[r];

for(int i=0;i<r;i++) t2[i]=0;

int p1, k1, p2, k2, i;

p1=p; k1=m; p2=m+1; k2=k; i=p1;

while(p1<=k1 && p2<=k2)

{

if(t[p1]<t[p2])

{

t2[i]=t[p1]; p1++;

}

else

{

t2[i]=t[p2]; p2++;

}

i++;

}

while(p1<=k1)

{

t2[i]=t[p1];

p1++; i++;

}

while(p2<=k2)

{

t2[i]=t[p2];

p2++; i++;

}

for(i=p;i<=k;i++)

t[i]=t2[i];

}

po wyczerpaniu p2

po wyczerpaniu p1

kopiowanie z tab.
tymcz. do oryg.

29/38

Sortowanie przez scalanie - przykład

30/38

Sortowanie – porównanie
efektywności metod, mały zbiór

187

195

196

scalanie

227

246

264

kopcowanie

75

137

55

szybkie

5757

3071

5

wstrząsanie

5599

3212

610

bąbelkowe

1430

607

76

wybieranie

2150

1129

46

wstawianie

Zbiór odwrotnie

uporz

ą

dkowany

Zbiór losowy

Zbiór

uporz

ą

dkowany

Typ sortowania

źródło: N. Wirth: „Algorytmy + struktury danych = programy”

n=256, czas podany w milisekundach, maszyna: CDC 6400

31/38

Sortowanie – porównanie
efektywności metod, duży zbiór

2,112

1,911

3,293

1,131

bąbelkowe

1,643

2,424

2,504

0,001

wstrząsanie

1,659

2,600

1,176

1,202

wybieranie

0,566

1,125

0,570

0,001

wstawianie

0,031

0,027

0,035

0,033

kopcowanie

0,027

0,024

0,031

0,026

scalanie

0,371

0,471

0,021

0,621

szybkie

Średnia

Zbiór odwrotnie

uporz

ądkowany

Zbiór

losowy

Zbiór

uporz

ądkowany

Typ

sortowania

źródło: własne, n=10000, czas podany w mikrosekundach,

32/38

Wyszukiwanie elementu tablicy o podanym
indeksie w nieuporządkowanym zbiorze



metody:



posortować zbiór i wyznaczyć szukany
element



wyznaczyć szukany element bez
całkowitego sortowania zbioru

33/38

Algorytm Hoare’a



podział tablicy na dwie części z zastosowaniem
wartości podziałowej, podobnie jak w
quicksort, z wartościami l=1, p=n, m=tab[k]
m - punkt podzia

ł

u, k – indeks szukanej wart.



otrzymuje się:



tab[k]

≤

m dla wszystkich k < i



tab[k]

≥

m dla wszystkich k > j



i > j

34/38

Algorytm Hoare’a - trzy przypadki



możliwe trzy przypadki:



wartość dzieląca jest zbyt mała, granica podziału poniżej szukanej
wartości k, proces podziału powtarzany jest dla tab[i]…tab[p]



wartość dzieląca za duża, operacja dzielenia powtarzana dla
przedziału tab[l]…tab[j]



j < k < i → element tab[k] dzieli tablicę na dwa zbiory w
wymaganej proporcji → koniec szukania



proces dzielenia powtarzany jest aż do wystąpienia
ostatniego przypadku

l

m

p

i

j

≤

≥

k

l

k

p

i

j

≤

≥

m

l

p

i

j

≤

≥

k=m

35/38

Algorytm Hoare’a - przykład

void szuk_elem(int t[], int r, int k)

{

int l,p,i,j,m,wtemp;

l=0; p=r-1;

while(l<p)

// dopóki indeksy nie miną się

{

m=t[k]; i=l; j=p;

// m-wartość podziałowa

do

{

while(t[i]<m) i++;

// szukanie 1. niemniejszego od m

while(t[j]>m) j--;

// szukanie 1. niewiększego od m

if(i<=j)

// zamiana wyszukanych powyżej

{ wtemp=t[i]; t[i]=t[j]; t[j]=wtemp; i++; j--; }

} while(i<=j);

// dopóki indeksy i oraz j nie miną się

if(j<k) l=i;

// zawężanie przedziału poszukiwań

if(i>k) p=j;

// zawężanie przedziału poszukiwań

}

}

36/38

Algorytm Hoare’a - przykład

81 zamieniane z 6, i++, j--

44 zamieniane z 73, i ust. się
na 73, j ust. się na 16

j<k => l=5, i=5, j=9

73 zamieniane z 70, i++, j--
i ust. się na 81, j ust. się na 59
i>k => p=6, i=l=5, j=6

59 zamieniane z 70, i++, j--
i ust. się na 70, j ust. się na 59
i>k => p=j=5, i=l=5,
j=p=5

l nie jest < p => koniec szukania

37/38

Algorytm Hoare’a - podsumowanie



średnia liczba porównań
Pr=n+n/2+n/4+…=2n



duże zbiory → znaczna różnica w stosunku
do metod sortowania (najlepsze klasy
N

∙

logN)



małe zbiory → brak wyraźnej różnicy
między metodą z sortowaniem

38

Dziękuję za uwagę