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.