L.Plawecki, 2004.r.
L.Plawecki, 2004.r.
L.Plawecki, 2004.r.
Plan zajęć
• Powtórzenie i sprawdzenie wiadomości
z poprzedniego ćwiczenia.
• Metody sortowania
– metoda prostego wyboru
– metoda prostego wstawiania
– prosta i zmodyfikowana metoda
bąbelkowa
• Szacowanie złożoności metod
sortowania
L.Plawecki, 2004.r.
Ćwiczenia
• Zaprojektuj (w pseudokodzie) i oszacuj
złożoność obliczeniową algorytmu:
–
wyszukującego w tablicy jednowymiarowej
element minimalny wraz z jego pozycją,
–
wyszukujący w tablicy dwuwymiarowej
element podany z klawiatury wraz z jego
pozycją.
Zakładamy, że tablice te są
różnowartościowe.
L.Plawecki, 2004.r.
Sortowanie
L.Plawecki, 2004.r.
Metody sortowania
• Metoda prostego wstawiania
• Metoda prostego wyboru
• Sortowanie bąbelkowe
• Metoda Shella
• Sortowanie stogowe
• Sortowanie szybkie
L.Plawecki, 2004.r.
Złożoność obliczeniowa
algorytmów sortowania.
Za operację dominującą przyjmuje
się porównania elementów.
Czasem analizuje się też
przestawienia elementów.
L.Plawecki, 2004.r.
Proste wstawianie
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3
i=4
i=5
i=6
i=7
i=2
L.Plawecki, 2004.r.
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4
i=5
i=6
i=7
i=2
Proste wstawianie
L.Plawecki, 2004.r.
Proste wstawianie
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5
i=6
i=7
i=2
L.Plawecki, 2004.r.
Proste wstawianie
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 19 06 67
i=6
i=7
i=2
L.Plawecki, 2004.r.
Proste wstawianie
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 18 06 67
i=6 12 18 42 44 55 94 06 67
i=7
i=2
L.Plawecki, 2004.r.
Proste wstawianie
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 18 06 67
i=6 12 18 42 44 55 94 06 67
i=7 06 12 18 42 44 55 94 67
i=2
L.Plawecki, 2004.r.
Proste wstawianie
44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 18 06 67
i=6 12 18 42 44 55 94 06 67
i=7 06 12 18 42 44 55 94 67
i=8 06 12 18 42 44 55 67 94
L.Plawecki, 2004.r.
Proste wstawianie
for i:= 2 to n do
begin
x=a[i];
{wstaw x w odpowiednim miejscu
a
1
...a
n
}
end
L.Plawecki, 2004.r.
Proste wstawianie
procedure ProsteWstawianie;
begin
for i:=2 to n do
{a[0] –dodatkowa składowa dla
wartownika}
begin x:=a[i]; a[0]:=x; j:=i;
{przesuwanie aż do znalezienia mniejszego lub
równego elementu}
while x<a[j] do begin a[j+1]:=a[j]; j:=j-1;
end;
a[j+1]=x;
end
end;
L.Plawecki, 2004.r.
Proste wstawianie
Złożoność obliczeniowa:
f(n) = 2+3+..+n = (n(n+1))/2 – 1 = 1/2(n
2
+n)-1
f(n ) = 1/2n
2
+ 1/2n - 1 = O(n
2
)
uzasadnienie :
funkcja f(n) jest zawsze mniejsza od np. n
2
(c=1) ,
gdyż z: 1/2n
2
+1/2n – 1 < n
2
wynika: -1/2(n
2
-n) -1<
0
co jest słuszne dla każdego n naturalnego,
gdyż n
2
-n jest wtedy zawsze nieujemne.
L.Plawecki, 2004.r.
Proste wybieranie
44 55 12 42 94
18
06 67
06 55 12 42 94
18
44 67
L.Plawecki, 2004.r.
Proste wybieranie
44 55 12 42 94
18
06 67
06 55 12 42 94
18
44 67
06 12 55 42 94
18
44 67
L.Plawecki, 2004.r.
Proste wybieranie
44
55 12 42 94
18
06 67
06
55 12 42 94
18
44 67
06
12 55 42 94
18
44 67
06
12 18 42 94
55
44 67
L.Plawecki, 2004.r.
Proste wybieranie
44
55 12 42 94
18
06 67
06
55 12 42 94
18
44 67
06
12 55 42 94
18
44 67
06
12 18 42 94
55
44 67
06
12 18 42 44
55
94 67
L.Plawecki, 2004.r.
Proste wybieranie
44
55 12 42 94
18
06 67
06
55 12 42 94
18
44 67
06
12 55 42 94
18
44 67
06
12 18 42 94
55
44 67
06
12 18 42 44
55
94 67
06
12 18 42 44
55
67 94
L.Plawecki, 2004.r.
Proste wybieranie
Procedure ProsteWybieranie
begin for i:=1 to n-1 do
begin k:=i; x:=a[i];
{szukanie elementu najmniejszego}
for j:=i+1 to n do
if a[j]<x then begin k:=j; x:=a[j] end
{zamiana elementu i z elementem
najmniejszym}
a[k]:=a[i]; a[i]:=x;
end
end
L.Plawecki, 2004.r.
Proste wybieranie
Złożoność obliczeniowa
)
(
)
(
2
1
2
1
2
)
1
(
)
(
1
...
)
2
(
)
1
(
)
(
2
2
n
n
O
n
f
n
n
n
n
f
n
n
n
f
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
i=
2
44 06
55 44
12 55
42 12
94 42
18 94
06 18
67 67
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
i=
2
i=
3
44 06 06
55 44 12
12 55 44
42 12 55
94 42 18
18 94 42
06 18 94
67 67 67
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
i=
2
i=
3
i=
4
44 06 06 06
55 44 12 12
12 55 44 18
42 12 55 44
94 42 18 55
18 94 42 42
06 18 94 67
67 67 67 94
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
i=
2
i=
3
i=
4
i=
5
44 06 06 06 06
55 44 12 12 12
12 55 44 18 18
42 12 55 44 42
94 42 18 55 44
18 94 42 42 55
06 18 94 67 67
67 67 67 94 94
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
i=
2
i=
3
i=
4
i=
5
i=
6
i=
7
i=
8
44 06 06 06 06
06 06 06
55 44 12 12 12
12 12 12
12 55 44 18 18
18 18 18
42 12 55 44 42
42 42 42
94 42 18 55 44
44 44 44
18 94 42 42 55
55 55 55
06 18 94 67 67
67 67 67
67 67 67 94 94
94 94 94
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
procedure SortowanieBąbelkowe
begin
for i=2 to n do
for j:=n downto i do
if a[j-1]>a[j] then
begin x:=a[j-1]; a[j-1]:=a[j];
a[j]:=x end
end
L.Plawecki, 2004.r.
Prosta zamiana
(sortowanie bąbelkowe)
Złożoność obliczeniowa
)
(
)
(
2
1
2
1
2
)
1
(
)
(
1
...
)
2
(
)
1
(
)
(
2
2
n
n
O
n
f
n
n
n
n
f
n
n
n
f
L.Plawecki, 2004.r.
Ćwiczenie 1
• W jaki sposób można ulepszyć
sortowanie bąbelkowe?
Zaproponuj ulepszony algorytm
i oszacuj jego złożoność
obliczeniową.
L.Plawecki, 2004.r.
Ćwiczenie 2.
Opracować algorytm który
pobiera kolejne elementy
składowe z tablicy A[1..n] i
umieszcza w tablicy B[1..n]
uporządkowane rosnąco
stosując metodę wstawiania
połówkowego i oszacuj
złożoność algorytmu.
L.Plawecki, 2004.r.
Ćwiczenie 2.
b(1) := a(1) { pierwszy element}
{drugi element}
If a(2) >= a(1) Then
b(2) := a(2)
Else begin
x := b(1); b(1) := a(2); b(2) := x
End ;
j = 2
For i = 3 To 10
If a(i) >= b(j) Then
j = j + 1: b(j) = a(i) {dodaj element na końcu b}
ElseIf a(i) <= b(1) Then
{przesuń o 1 wszystkie elementy }
b(1) = a(i)
j = j + 1
Else
{Wstawianie połówkowe}
End;
L.Plawecki, 2004.r.
Ćwiczenie 3.
Oszacuj liczbę kroków procedury zagadka :
procedure zagadka
begin
for i:=sqr(n) downto 1 do
if odd(i) then
for j:=1 to i do
for k:=i+1 to n do x:=x+1;
end;
gdzie funkcja odd sprawdza czy argument
jest parzysty a sqr oblicza pierwiastek
kwadratowy.
L.Plawecki, 2004.r.
Ćwiczenie 4
Stosując wyszukiwanie sekwencyjne w tablicy
nieposortowanej bądź binarne w tablicy
posortowanej wybieramy pomiędzy czasem
wyszukiwania, a czasem przetwarzania
wstępnego. Jak wiele wyszukiwań binarnych
trzeba wykonać w najgorszym przypadku
danych w tablicy n-elementowej, żeby opłacił
się czas potrzebny na wstępne posortowanie
tablicy ? Przyjmując, że współczynniki
proporcjonalności złożoności są równe 1,
odpowiedź sformułuj w terminach oszacowań
asymptotycznych.
L.Plawecki, 2004.r.
Literatura
- Aho A.V., Hopcroft J.E., Ullman
J.D.: Projektowanie i analiza
algorytmÛw komputerowych ñ
PWN,
Warszawa 1983.
- Banachowski L., Diks K., Rytter
W.: Algorytmy i struktury
danych ñ WNT, Warszawa 2001.
L.Plawecki, 2004.r.
Literatura
-Wirth N.:
Algorytmy + struktury danych
=programy
WNT, Warszawa 1989.
- Zasoby sieci Internet.