Algorytmy i struktury danych
wykład 4
Algorytmy sortowania cz.2
1
Plan prezentacji
sortowanie metodą drzewa
sortowanie metodą kopcowania (Heapsort)
sortowanie metodą scalania
porównanie poznanych metod sortowania
wyszukiwanie wskazanego elementu tablicy
2/38
Poznane metody sortowania
przez wstawianie
przez wybieranie
bąbelkowe
przez wstrząsanie (shakesort)
szybkie (quicksort)
3/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
4/38
Sortowanie drzewiaste  budowa
drzewa
1
2 1
1
2 4 9
7 2 5 4 8 1 9 10
5/38
Sortowanie drzewiaste  usunięcie
korzenia- elementu najmniejszego
-
2 -
-
2 4 9
7 2 5 4 8 - 9 10
6/38
Sortowanie drzewiaste  wybór nowego
korzenia- elementu najmniejszego
2
2 8
8
2 4 9
7 2 5 4 8 - 9 10
7/38
Sortowanie drzewiaste  analiza
po n krokach drzewo jest puste tablica
posortowana
liczba porównań Pr=log2n
cały proces sortowania wymaga n"logn
operacji prostych oraz n operacji
budowania drzewa
8/38
Sortowanie przez kopcowanie
(heap sort)
jest ulepszoną wersją sortowania
drzewiastego
opiera się na pojęciu kopca
9/38
Kopiec (heap) - definicja
ciąg elementów hl, hl+1,& ,hp spełniających zależności:
hi e" h2i, hi e" h2i+1 dla każdego i = l& p/2
h1 h1=max(hl,& ,hn)
h2 h3
h6
h4 h5 h7
h8 h9 h10 h11 h12
10/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)] e" h[i] dla każdego węzła
i nie będącego korzeniem
11/38
Zamiana listy na kopiec
Elementy listy: 7,2,6,4,8,1,9,10,3,5
7
2 6
1
4 8 9
10 3 5
12/38
Przywracanie własności kopca
procedura wywoływana gdy jeden z elementów
kopca nie spełnia zależności h[ojciec(i)] e" h[i]
polega na przesunięciu elementu na niższe poziomy
drzewa (kopca) w ten sposób, aby poddrzewo
zaczepione w danym węz
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
13/38
Budowa kopca
7
2 6
1
1
10 8 9
4 3 5
7
2
2 9
1
10 8 6
4 3 5
14/38
Budowa kopca
7
10 9
3
1
4 8 6
2 3 5
10
4
8 9
1
4 7 6
2 3 5
15/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
16/38
Sortowanie danych  1. krok
10
zamiana elementu
największego i
ostatniego
8 9
1
4 7 6
5
2 3 5
przywracanie
właściwości kopca
8 9
1
4 7 6
2 3 10
17/38
Sortowanie danych  2. krok
9
8 6
1
1
4 7 5
2 3 10
8
2
7 6
1
4 3 5
2 9 10
18/38
Sortowanie danych 3. i 4. krok
7
4 6
3
1
2 3 5
8 9 10
6
4
4 5
1
2 3 7
8 9 10
19/38
Sortowanie danych  ostatni krok
1
2 3
9
6
4 5 7
8 9 10
1 2 3 4 5 6 7 8 9 10
20/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
}
21/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(jif(wtemp>=t[j-1]) break; //ojciec>=syn, więc nie ma zamiany
else //ojciec{
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
}
22/38
Sortowanie przez kopcowanie - przykład
budowa
kopca
posortowana
część tablicy
23/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)
24/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)
25/38
Sortowanie przez scalanie
void sort_scalanie(int t[], int p, int k)
{
podział na dwie podtablice
int m;
if(p{
wywołania rekurencyjne
m=(p+k)/2;
sort_scalanie(t,p,m);
sort_scalanie(t,m+1,k);
scalanie(t,n,p,m,k);
}
scalenie podtablic
}
26/38
Scalanie - opis
wykonywane jest dla podtablic uzyskanych w
procesie dzielenia, w odwrotnej kolejności
scalanie podtablic t1:{xp..xm} oraz
t2{xm+1..xk} do tablicy t:{xp..xk} odbywa się
następująco
i= xp..xm , j=xm+1..xk
jeżeli t1[i]<=t2[j], wstawianie t1[i] do t; i:=i+1
jeżeli t2[j]27/38
Scalanie - procedura
po wyczerpaniu p2
void scalanie( int t[], int r, int p,
while(p1<=k1)
int m, int k)
{
{
int* t2=new int[r];
t2[i]=t[p1];
for(int i=0;ip1++; i++;
int p1, k1, p2, k2, i;
} po wyczerpaniu p1
p1=p; k1=m; p2=m+1; k2=k; i=p1;
while(p2<=k2)
while(p1<=k1 && p2<=k2)
{
{
if(t[p1]t2[i]=t[p2];
{
p2++; i++;
t2[i]=t[p1]; p1++;
}
}
for(i=p;i<=k;i++)
else
t[i]=t2[i];
{
}
t2[i]=t[p2]; p2++;
kopiowanie z tab.
}
i++; tymcz. do oryg.
}
28/38
Sortowanie przez scalanie - przykład
29/38
Sortowanie  porównanie
efektywności metod, mały zbiór
Zbiór Zbiór odwrotnie
Typ sortowania Zbiór losowy
uporządkowany uporządkowany
wstawianie 46 1129 2150
wybieranie 76 607 1430
bąbelkowe 610 3212 5599
wstrząsanie 5 3071 5757
szybkie 55 137 75
kopcowanie 264 246 227
scalanie 196 195 187
z
ródło: N. Wirth:  Algorytmy + struktury danych = programy
n=256, czas podany w milisekundach, maszyna: CDC 6400
30/38
Sortowanie  porównanie
efektywności metod, duży zbiór
Typ Zbiór Zbiór Zbiór odwrotnie
Średnia
sortowania uporządkowany losowy uporządkowany
szybkie 0,621 0,021 0,471 0,371
scalanie 0,026 0,031 0,024 0,027
kopcowanie 0,033 0,035 0,027 0,031
wstawianie 0,001 0,570 1,125 0,566
wybieranie 1,202 1,176 2,600 1,659
wstrząsanie 0,001 2,504 2,424 1,643
bąbelkowe 1,131 3,293 1,911 2,112
z
ródło: własne, n=10000, czas podany w mikrosekundach,
31/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
32/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] d" m dla wszystkich k < i
tab[k] e" m dla wszystkich k > j
i > j
33/38
Algorytm Hoare a - trzy przypadki
d" e"
możliwe trzy przypadki:
l j m k i p
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
d" e"
przedziału tab[l]& tab[j]
l j k m i p
j < k < i element tab[k] dzieli tablicę na dwa zbiory w
wymaganej proporcji koniec szukania
d" e"
l j k=m i p
proces dzielenia powtarzany jest aż do wystąpienia
ostatniego przypadku
34/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{
m=t[k]; i=l; j=p; // m-wartość podziałowa
do
{
while(t[i]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(jif(i>k) p=j; // zawężanie przedziału poszukiwań
}
}
35/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 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
36/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 wyraz
nej różnicy
między metodą z sortowaniem
37/38
Dziękuję za uwagę
38