INF2 2009 Wykl 04 Zaoczne 4na1

background image

Informatyka 2

Informatyka 2

Politechnika Białostocka

Politechnika Białostocka -- Wydział Elektryczny

Wydział Elektryczny

Elektrotechnika, semestr III, studia niestacjonarne I stopnia (zaoczne)

Elektrotechnika, semestr III, studia niestacjonarne I stopnia (zaoczne)

Rok akademicki 2009/2010

Rok akademicki 2009/2010

Wykład nr 4 (11.12.2009)

Wykład nr 4 (11.12.2009)

dr inż. Jarosław Forenc

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

2/55

Plan wykładu nr 4

Plan wykładu nr 4

Operacje na wektorach i macierzach

normy wektorów i macierzy

obliczanie wartości wyznacznika macierzy

Sortowanie

sortowanie przez proste wstawianie

sortowanie przez proste wstawianie

sortowanie przez proste wybieranie

sortowanie bąbelkowe

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

3/55

Normy wektora

Normy wektora

Definicja:

norma wektora x

(oznaczenie

||x||

) jest liczbą, stanowiącą w pewnym sensie

miarę tego wektora

do najczęściej stosowanych norm wektora należą:

norma maksimum:

norma maksimum:

norma pierwsza:

norma druga (euklidesowa):

gdzie

n

jest liczbą elementów wektora

(1)

(2)

i

n

i

x

=

1

max

x

=

=

n

i

i

x

1

1

x

=

=

n

i

i

x

1

2

2

x

(3)

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

4/55

Normy wektora

Normy wektora

Przykład:

dany jest wektor:

wartości norm wynoszą:

norma maksimum:

[

]

2

1

8

6

4

5

3

=

x

norma pierwsza:

norma druga (euklidesowa):

i

n

i

x

=

1

max

x

=

=

n

i

i

x

1

1

x

=

=

n

i

i

x

1

2

2

x

8

=

x

29

2

1

8

6

4

5

3

1

=

+

+

+

+

+

+

=

x

45

,

12

155

2

1

)

8

(

6

)

4

(

5

3

2

2

2

2

2

2

2

2

=

=

+

+

+

+

+

+

=

x

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

5/55

Normy wektora

Normy wektora -- program w C (1/2)

program w C (1/2)

/*

Name: norma_wektor.c

Copyright: Politechnika Białostocka, Wydział Elektryczny

Author: Jarosław Forenc (jarekf@pb.edu.pl)

Date: 20-03-2007

Description: Obliczanie norm wektora

*/

#include <stdio.h>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define N 7

int main()

{

/* Wektor */

float x[N] = {3, 5, -4, 6, -8, 1, 2};

float norma_max, norma1, norma2;

int i;

/* Norma maksimum */

norma_max = fabs(x[0]);

for (i=1; i<N; i++)

if (norma_max < fabs(x[i]))

norma_max = fabs(x[i]);

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

6/55

Normy wektora

Normy wektora -- program w C (2/2)

program w C (2/2)

/* Norma pierwsza */

norma1 = 0;

for (i=0; i<N; i++)

norma1 = norma1 + fabs(x[i]);

/* Norma druga(euklidesowa) */

norma2 = 0;;

for (i=0; i<N; i++)

norma2 = norma2 + x[i]*x[i];

Norma maksimum:

8

Norma pierwsza:

29

Norma euklidesowa: 12.4499

norma2 = norma2 + x[i]*x[i];

norma2 = sqrt(norma2);

/* Wyswietlenie wynikow */

printf("Norma maksimum: %g\n",norma_max);

printf("Norma pierwsza: %g\n",norma1);

printf("Norma euklidesowa: %g\n",norma2);

system("pause");

return 0;

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

7/55

Normy macierzy

Normy macierzy

Definicja:

norma macierzy A

(oznaczenie ||A||) jest liczbą, stanowiącą w pewnym sensie

miarę tej macierzy

do najczęściej stosowanych norm macierzy należą:

norma nieskończoność:

norma nieskończoność:

norma pierwsza:

norma euklidesowa (nazywana też normą Frobeniusa):

(4)

(5)

(6)

=

=

n

j

ij

n

i

a

1

1

max

A

=

=

n

i

ij

n

j

a

1

1

1

max

A

∑∑

=

=

=

n

i

n

j

ij

E

a

1

1

2

A

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

8/55

Normy macierzy

Normy macierzy

Przykład:

17

15

3

5

7

3

17

9

6

2

2

12

4

5

3

1

max

3

5

7

9

6

2

4

5

3

1

1

=

=

+

+

=

+

+

=

+

+

=

=

=

A

A

A

wiersz

wiersz

wiersz

a

n

j

ij

n

i

16

16

3

9

4

3

16

5

6

5

2

12

7

2

3

1

max

3

5

7

9

6

2

4

5

3

1

1

1

1

=

=

+

+

=

+

+

=

+

+

=

=

=

A

A

A

kolumna

kolumna

kolumna

a

n

i

ij

n

j

937

,

15

3

5

7

9

6

2

4

5

3

3

5

7

9

6

2

4

5

3

2

2

2

2

2

2

2

2

2

1

1

2

=

+

+

+

+

+

+

+

+

+

=

=

=

∑∑

=

=

E

n

i

n

j

ij

E

a

A

A

A

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

9/55

Normy macierzy

Normy macierzy -- program w C (1/2)

program w C (1/2)

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define N 3

int main()

{

{

float A[N][N] = {{ 3, -5, 4},

{ 2, 6, -9},

{ 7, 5, 3}};

float norma_inf, norma1, norma_euk, suma;

int i, j;

/* Norma nieskonczonosc */

norma_inf = 0;

for (i=0; i<N; i++)

{

suma = 0;

for (j=0; j<N; j++)

suma = suma + fabs(A[i][j]);

if (suma > norma_inf)

norma_inf = suma;

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

10/55

Normy macierzy

Normy macierzy -- program w C (2/2)

program w C (2/2)

/* Norma pierwsza */

norma1 = 0;

for (j=0; j<N; j++)

{

suma = 0;

for (i=0; i<N; i++)

suma = suma + fabs(A[i][j]);

if (suma > norma1)

Norma nieskonczonosc:

17

Norma pierwsza:

16

Norma euklidesowa:

15.9374

if (suma > norma1)

norma1 = suma;

}

/* Norma euklidesowa */

norma_euk = 0;

for (i=0; i<N; i++)

for (j=0; j<N; j++)

norma_euk = norma_euk + A[i][j]*A[i][j];

norma_euk = sqrt(norma_euk);

/* Wyswietlenie wynikow */

printf("Norma nieskonczonosc: %g\n",norma_inf);

printf("Norma pierwsza: %g\n",norma1);

printf("Norma euklidesowa: %g\n",norma_euk);

system("pause");

return 0;

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

11/55

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

Wyznacznik:

wyznacznikiem

stopnia

n

macierzy kwadratowej

A

o

n

wierszach i

n

kolumnach

nazywamy liczbę rzeczywistą, oznaczaną jako

det A

lub

|A|

:

n

n

a

a

a

a

a

a

L

L

2

22

21

1

12

11

det

=

=

A

A

oznaczenie

det

jest skrótem od słowa

determinant

w prosty sposób można obliczyć wyznacznik drugiego stopnia:

nn

n

n

n

a

a

a

a

a

a

L

M

O

M

M

L

2

1

2

22

21

det

=

=

A

A

21

12

22

11

22

21

12

11

det

a

a

a

a

a

a

a

a

=

=

A

(7)

(8)

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

12/55

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

wyznacznik trzeciego stopnia obliczany jest według tzw.

reguły Sarrusa

(

schematu Sarrusa

):

33

32

31

23

22

21

13

12

11

det

a

a

a

a

a

a

a

a

a

=

A

(9)

dopisujemy do prawej strony wyznacznika dwie pierwsze kolumny:

obliczamy sumę iloczynów wzdłuż zielonych strzałek i odejmujemy od niej sumę
iloczynów wzdłuż czerwonych strzałek:

32

31

33

32

31

22

21

23

22

21

12

11

13

12

11

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

33

21

12

32

23

11

31

22

13

32

21

13

31

23

12

33

22

11

det

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

+

+

=

A

(10)

(11)

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

13/55

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

to samo można otrzymać dopisując do wyznacznika,
zamiast dwóch pierwszych kolumn, dwa pierwsze
wiersze pod wyznacznikiem

23

22

21

13

12

11

33

32

31

23

22

21

13

12

11

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

21

12

33

11

32

23

31

22

13

23

12

31

13

32

21

33

22

11

det

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

+

+

=

A

(12)

Przykłady:

obliczanie wyznacznika drugiego stopnia:

obliczanie wyznacznika trzeciego stopnia:

2

4

6

1

4

2

3

2

1

4

3

=

=

=

3

3

4

1

1

0

3

2

1

2

3

3

2

2

0

4

1

1

1

1

0

2

3

1

4

2

3

1

=

+

+

=

21

12

33

11

32

23

31

22

13

23

12

31

13

32

21

33

22

11

det

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

+

+

=

A

(12)

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

14/55

do obliczenia wyznacznika stopnia czwartego i większego stosuje się

twierdzenie

Laplace’a

(

rozwinięcie Laplace’a

):

Dla dowolnej macierzy kwadratowej

A

stopnia

n

zachodzi:

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

in

in

i

i

i

i

n

j

ij

ij

a

a

a

a

A

A

A

A

A

+

+

+

=

=

=

L

2

2

1

1

1

)

(

det

(13)

gdzie:

det A

- wyznacznik macierzy

A

a

ij

- element w i-tym wierszu i j-tej kolumnie

A

ij

- dopełnienie algebraiczne elementu

a

ij

dopełnienie algebraiczne elementu

a

ij

macierzy kwadratowej

A

wymiaru

n

jest to wyznacznik macierzy powstałej z

A

przez skreślenie jej

i

-tego wiersza

i

j

-tej kolumny pomnożony przez

(-1)

i+j

prawa strona wzoru (13) nazywana jest rozwinięciem względem i-tego wiersza

j

=

1

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

15/55

obliczanie wyznacznika czwartego stopnia - rozwijamy względem dowolnego
wiersza, np. pierwszego

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

+

+

=

=

+

+

1

3

2

1

0

4

2

1

2

)

1

(

1

1

3

1

1

0

3

2

1

3

)

1

(

0

1

0

3

4

2

1

3

2

1

2

1

0

det

2

1

1

1

A

po rozwinięciu względem wybranego wiersza otrzymujemy

n

wyznaczników

o stopniu obniżonym o jeden

zastosowanie rozwinięcia Laplace’a jest procesem czasochłonnym - liczba mnożeń
potrzebnych do obliczenia wyznacznika

n

-tego stopnia wynosi

n!

dla

n=15

i procesora wykonującego

10

9

mnożeń na sekundę obliczenie wartości

wyznacznika zajmie ok. 20 923 s

349 min.

6 godz.

1

3

2

1

3

1

1

3

1

2

3

1

2

0

3

4

1

3

2

)

1

(

1

1

1

2

1

3

4

2

3

2

)

1

(

2

4

1

3

1

+

+

+

+

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

16/55

w analogiczny sposób można sformułować wyznacznik poprzez rozwinięcie
względem j-tej kolumny:

korzystając z faktu, iż dodanie lub odjęcie od dowolnego wiersza / kolumny innego
wiersza / kolumny macierzy nie zmienia wartości wyznacznika, to można tak

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

nj

nj

j

j

j

j

n

i

ij

ij

a

a

a

a

A

A

A

A

A

+

+

+

=

=

=

L

2

2

1

1

1

)

(

det

(14)

wiersza / kolumny macierzy nie zmienia wartości wyznacznika, to można tak
przekształcić macierz, aby w pewnym wierszu lub kolumnie było jak najwięcej
elementów zerowych

od wiersza drugiego odejmujemy wiersz pierwszy podzielony przez 2

od wiersza trzeciego odejmujemy wiersz pierwszy pomnożony przez 2

od wiersza czwartego odejmujemy wiersz pierwszy (pomnożony przez 1)

=

=

=

1

2

4

0

0

4

6

0

2

3

2

0

2

2

4

2

1

2

2

/

1

4

0

2

4

0

2

4

3

4

4

1

2

2

4

2

1

4

4

1

3

3

1

2

2

w

w

w

w

w

w

w

w

w

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

17/55

w analogiczny sposób „zerujemy” elementy w drugiej i trzeciej kolumnie

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

=

=

3

8

0

0

6

5

0

0

2

3

2

0

2

2

4

2

)

2

(

)

3

(

1

2

4

0

0

4

6

0

2

3

2

0

2

2

4

2

2

4

4

2

3

3

w

w

w

w

w

w

wyznacznik będzie równy iloczynowi elementów znajdujących się na głównej
przekątnej:

3

8

0

0

1

2

4

0

=

6

,

6

0

0

0

6

5

0

0

2

3

2

0

2

2

4

2

)

5

/

8

(

3

8

0

0

6

5

0

0

2

3

2

0

2

2

4

2

3

4

4

w

w

w

132

)

6

,

6

(

5

2

2

det

=

=

A

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

18/55

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

przedstawiony proces sprowadzenie macierzy do postaci trójkątnej górnej poprzez
wykonanie odpowiednich operacji na wierszach / kolumnach macierzy nazywa się

eliminacją Gaussa

:

=

→

=

,

2

,

22

1

12

11

2

22

21

1

12

11

0

n

n

n

n

a

a

a

a

a

a

a

a

a

a

a

M

O

M

M

L

L

M

O

M

M

L

L

A

A

(15)

wyznacznik macierzy jest w takim przypadku iloczynem wyrazów na głównej
przekątnej i można obliczyć go na podstawie wzoru:

=

→

=

,

2

1

0

0

nn

nn

n

n

a

a

a

a

L

M

O

M

M

L

M

O

M

M

A

A

,

,

22

11

1

det

nn

n

i

ii

a

a

a

a

=

=

=

K

A

(15)

(16)

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

19/55

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika

opiszmy przedstawione przekształcenie za pomocą wzorów:

=

→

=

)

(

)

2

(

2

)

2

(

22

)

1

(

1

)

1

(

12

)

1

(

11

)

1

(

)

1

(

)

1

(

)

1

(

2

)

1

(

22

)

1

(

21

)

1

(

1

)

1

(

12

)

1

(

11

0

0

0

n

n

n

n

n

a

a

a

a

a

a

a

a

a

a

a

a

a

a

a

L

M

O

M

M

L

L

L

M

O

M

M

L

L

A

A

)

(

)

1

(

)

1

(

2

)

1

(

1

0

0

n

nn

nn

n

n

a

a

a

a

L

L

n

k

k

j

i

n

k

a

a

a

a

a

k

kk

k

kj

k

ik

k

ij

k

ij

...,

,

2

,

1

,

1

...,

,

2

,

1

,

)

(

)

(

)

(

)

(

)

1

(

+

+

=

=

=

+

/* Tworzenie macierzy trójk

ą

tnej górnej */

for (k=0; k<N-1; k++)

{

for (i=k+1; i<N; i++)

for (j=N-1; j>=k; j--)

A[i][j] = A[i][j] - A[i][k]*A[k][j]/A[k][k];

}

(17)

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

20/55

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika -- program w C (1/2)

program w C (1/2)

/*

Name: Wyznacznik-Gauss.c

Copyright: Politechnika Białostocka, Wydział Elektryczny

Author: Jarosław Forenc (jarekf@pb.edu.pl)

Date: 20-03-2007

Description: Obliczanie warto

ś

ci wyznacznika dowolnego stopnia:

- zastosowanie eliminacji Gaussa

*/

*/

#include <stdio.h>

#include <stdlib.h>

#define N 4 /* Stopie

ń

wyznacznika */

int main()

{

/* Macierz */

float A[N][N] = {{2, 4, 2, 2},

{1, 4, 4, 3},

{4, 2, 0, 4},

{2, 0, 4, 1}};

float iloczyn = 1.0;

int i,j,k;

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

21/55

/* Tworzenie macierzy trójk

ą

tnej górnej */

for (k=0; k<N-1; k++)

{

for (i=k+1; i<N; i++)

for (j=N-1; j>=k; j--)

A[i][j] = A[i][j] - A[i][k]*A[k][j]/A[k][k];

}

/* Obliczenie warto

ś

ci wyznacznika */

Obliczanie wartości wyznacznika

Obliczanie wartości wyznacznika -- program w C (2/2)

program w C (2/2)

det A = -132

/* Obliczenie warto

ś

ci wyznacznika */

for (i=0; i<N; i++)

iloczyn = iloczyn * A[i][i];

/* Wy

ś

wietlenie rozwi

ą

zania */

printf("det A = %g\n",iloczyn);

system("pause");

return 0;

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

22/55

Sortowanie

Sortowanie

sortowanie

polega na

uporządkowaniu

zbioru danych względem pewnych cech

charakterystycznych każdego elementu tego zbioru

najczęstszym przypadkiem jest sortowanie względem wartości każdego elementu,
np. sortowanie liczb, sortowanie słów

w przypadku liczb, sortowanie polega na znalezieniu kolejności liczb zgodnej
z relacją

lub

z relacją

lub

Przykład:

tablica nieposortowana:

tablica posortowana zgodnie z relacją

(od najmniejszej do największej liczby):

tablica posortowana zgodnie z relacją

(od największej do najmniejszej liczby):

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

23/55

Sortowanie

Sortowanie

w przypadku słów (nazw) sortowanie polega na ustawieniu ich w porządku

słownikowym

(lub

alfabetycznym

) zwanym także

leksykograficznym

Przykład:

tablica nieposortowana:

tablice posortowane:

porównanie nazw może być sprowadzone do porównywania ich liczbowych kodów

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

24/55

Sortowanie

Sortowanie

w praktyce sortowanie sprowadza się do porządkowanie danych na podstawie
porównania - element stosowany w porównaniu nazywa się

kluczem

Przykład:

tablica nieposortowana (imię, nazwisko, wiek):

tablica posortowana (klucz - nazwisko):

tablica posortowana (klucz - wiek):

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

25/55

Sortowanie

Sortowanie

Po co stosować sortowanie?

posortowane elementy można szybciej zlokalizować

posortowane elementy można przedstawić w bardziej czytelny sposób, np.

kolejność alfabetyczna nazwisk

przedstawienie cen produktów od najniższej do najwyższej

przedstawienie cen produktów od najniższej do najwyższej

Klasyfikacje algorytmów sortowania

złożoność obliczeniowa algorytmu

- zależność liczby wykonywanych operacji

w stosunku do liczebności sortowanego zbioru

n

proste algorytmy sortowania mają złożoność

O(n

2

)

dobre algorytmy sortowania mają złożoność

O(n log n)

oceniając wydajność algorytmu często analizuje się najgorszy, najlepszy
i średni przypadek

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

26/55

Notacja O

Notacja O

notacja O

stosowana jest do porównywania wydajności różnych algorytmów

notacja ta wyraża złożoność matematyczną algorytmu

w notacji tej po literze

O

występuje wyrażenie w nawiasach zawierające literę

n

,

która oznacza liczbę elementów, na której działa algorytm

oceniając złożoność algorytmu bierze się pod uwagę liczbę wykonywanych

oceniając złożoność algorytmu bierze się pod uwagę liczbę wykonywanych
w nim elementarnych operacji, np. dodawanie, mnożenie, porównywanie

Przykład:

O(n)

- złożoność algorytmu jest prostą funkcją liczby elementów

-

(jeśli sortowanie 1000 elementów zajmuje 1 s, to sortowanie

- (

2000 elementów zajmie 2 s)

O(n

2

)

- czas konieczny do wykonania algorytmu rośnie wraz z kwadratem

-

liczby elementów

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

27/55

Notacja O

Notacja O

porównanie najczęściej występujących złożoności:

Elementy

Elementy

O(log

O(log n)

n)

O(n)

O(n)

O(n

O(n log

log n)

n)

O(n

O(n

2

2

))

O(2

O(2

n

n

))

10

3

10

33

100

1024

100

7

100

664

10 000

1,27

10

30

O(log n)

- złożoność logarytmiczna

O(n)

- złożoność liniowa

O(n log n)

- złożoność liniowo-logarytmiczna

O(n

2

)

- złożoność kwadratowa

O(2

n

)

- złożoność wykładnicza

100

7

100

664

10 000

1,27

10

1 000

10

1 000

9 966

1 000 000

1,07

10

301

10 000

13

10 000

132 877

100 000 000

1,99

10

3010

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

28/55

Klasyfikacje algorytmów sortowania

Klasyfikacje algorytmów sortowania

Złożoność pamięciowa:

złożoność pamięciowa

jest to wielkość zasobów zajmowanych przez algorytm

w algorytmach wykorzystujących technikę sortowania

w miejscu

wielkość

zestawu danych podczas sortowania nie zmienia się

algorytmy nie wykorzystujące techniki sortowania w miejscu wymagają podczas
sortowania znaczniej więcej miejsca w pamięci komputera do przechowywania

sortowania znaczniej więcej miejsca w pamięci komputera do przechowywania
danych

Sortowanie zewnętrzne i wewnętrzne:

sortowanie zewnętrzne

(sortowanie plików) - algorytmy stosowane, gdy nie jest

możliwe jednoczesne umieszczenie wszystkich elementów zbioru sortowanego
w pamięci komputera

sortowanie wewnętrzne

odbywa się w pamięci komputera

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

29/55

Klasyfikacje algorytmów sortowania

Klasyfikacje algorytmów sortowania

Stabilność algorytmu:

algorytm jest nazywany

stabilnym

, jeśli podczas sortowania zachowuje kolejność

występowania elementów o tym samym kluczu

Przykład:

tablica nieposortowana (imię, nazwisko, wiek):

tablica nieposortowana (imię, nazwisko, wiek):

tablica posortowana algorytmem stabilnym (klucz - wiek):

tablica posortowana algorytmem niestabilnym (klucz - wiek):

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

30/55

Metody sortowania

Metody sortowania

Uwagi do opisu algorytmów sortowania:

w opisie algorytmów sortowania będą używane tablice liczb całkowitych

wartość każdego sortowanego elementu jest jednocześnie kluczem sortowania

analizując daną metodę będziemy brali pod uwagę liczbę porównań, w której
uczestniczą elementy sortowanej tablicy

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

31/55

Sortowanie przez proste wstawianie

Sortowanie przez proste wstawianie

sortowanie przez proste wstawianie

(ang. insertion sort) jest podstawowym

algorytmem sortowania, łatwym do zrozumienia i implementacji

algorytm polega na pobieraniu kolejnego elementu z danych wejściowych
i wstawianiu go na odpowiednie miejsce w wynikach

Algorytm metody

:

elementy są umownie podzielone na ciąg wynikowy:

a

1

,a

2

,…,a

i-1

i ciąg źródłowy:

a

i

,a

i+1

,…,a

n

w i-tym kroku pobieramy element z ciągu źródłowego

a

i

porównujemy ten element z kolejnymi elementami z ciągu wynikowego:

a

i-1

,a

i-2

,…

porównywanie kończymy, gdy porównywany element jest mniejszy lub równy
elementowi

a

i

lub dojdziemy do początku ciągu wynikowego

wstawiamy element

a

i

w odpowiednim miejscu ciągu wynikowego

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

32/55

Sortowanie przez proste wstawianie

Sortowanie przez proste wstawianie

Przykład

:

Funkcja w języku C:

void InsertionSort(int tab[])

{

int i,j,tmp;

for (i=1; i<N; i++)

{

{

j=i;

tmp=tab[i];

while (tab[j-1]>tmp && j>0)

{

tab[j]=tab[j-1];

j--;

}

tab[j]=tmp;

}

}

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

33/55

Sortowanie przez proste wstawianie

Sortowanie przez proste wstawianie

Uwagi

:

złożoność algorytmu:

O(n

2

)

w najgorszym przypadku każdy element powoduje jednokrotne przestawienie wszystkich
poprzedzających go elementów, a wtedy liczba porównań wynosi:

n

(n-1)

+

wydajny dla danych wstępnie posortowanych

+

+

wydajny dla zbiorów o niewielkiej liczebności

+

małe zasoby zajmowane podczas pracy (sortowanie w miejscu)

+

stabilny - zachowuje oryginalną kolejność takich samych elementów

+

prosty w implementacji

mała efektywność dla średniej i dużej ilości danych

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

34/55

Sortowanie przez proste wybieranie

Sortowanie przez proste wybieranie

sortowanie przez proste wybieranie

(ang. selection sort), nazywane także

sortowaniem przez selekcję, jest jedną z prostszych metod sortowania

metoda ta polega na wyszukaniu elementu, który ma się znaleźć na zadanej
pozycji i na zamianie miejscami z tym elementem, który jest tam obecnie

Algorytm metody

:

zaczynając od elementu pierwszego, szukamy w tablicy elementu o najmniejszej
wartości

po znalezieniu takiego elementu zamieniamy go miejscami z pierwszym
elementem

następnie szukamy elementu najmniejszego zaczynając od drugiego elementu

po znalezieniu elementu o najmniejszej wartości zamieniamy go z drugim
elementem

powtarzamy powyższe operacje do momentu, aż w tablicy pozostanie tylko
jeden element

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

35/55

Sortowanie przez proste wybieranie

Sortowanie przez proste wybieranie

Przykład

:

Funkcja w języku C:

void SelectionSort(int tab[])

{

int i,j,k,tmp;

for (i=0;i<N-1;i++)

{

{

k=i;

for (j=i+1; j<N; j++)

if (tab[k]>tab[j])

k = j;

tmp = tab[i];

tab[i] = tab[k];

tab[k] = tmp;

}

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

36/55

Sortowanie przez proste wybieranie

Sortowanie przez proste wybieranie

Uwagi

:

złożoność algorytmu:

O(n

2

)

+

szybki w sortowaniu niewielkich tablic

+

małe zasoby zajmowane podczas pracy (sortowanie w miejscu)

+

+
+

prosty w implementacji

liczba porównań elementów jest niezależna od początkowego rozmieszczenia
elementów w tablicy (takie zachowanie algorytmu nazywane jest

neutralnym

lub

niewrażliwym

)

w algorytmie może zdarzyć się, że wykonywana jest zamiana tego samego
elementu ze sobą

w przedstawionej postaci algorytm jest niestabilny

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

37/55

Sortowanie przez proste wybieranie

Sortowanie przez proste wybieranie

Uwagi

:

uczynienie algorytmu stabilnym wymaga tylko jednej zmiany w kodzie programu

/* algorytm niestabilny */

for (i=0;i<N-1;i++)

{

/* algorytm stabilny */

for (i=0;i<N-1;i++)

{

{

k=i;

for (j=i+1; j<N; j++)

if (tab[k]>tab[j])

k = j;

tmp = tab[i];

tab[i] = tab[k];

tab[k] = tmp;

}

{

k=i;

for (j=i+1; j<N; j++)

if (tab[k]>=tab[j])

k = j;

tmp = tab[i];

tab[i] = tab[k];

tab[k] = tmp;

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

38/55

Sortowanie bąbelkowe

Sortowanie bąbelkowe

sortowanie bąbelkowe

(ang. bubble sort), nazywane także

sortowaniem

pęcherzykowym

lub

sortowaniem przez prostą zamianę

(ang. straight exchange)

polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności
jeśli jest to konieczne

nazwa metody wzięła się stąd, że kolejne porównania powodują „wypychanie”
kolejnego największego elementu na koniec („wypłynięcie największego bąbelka”)

Algorytm metody

:

porównujemy pierwszy i drugi element tabeli i jeśli trzeba to zamieniamy je
miejscami, następnie porównujemy drugi i trzeci element i jeśli jest to konieczne,
to zamieniamy je miejscami, itd.

powyższe operacje wykonujemy, aż dojdziemy do końca tabeli

następnie ponownie rozpoczynamy porównywanie elementów od początku tabeli
(element pierwszy z drugim, drugi z trzecim, itd. aż dojdziemy do końca tabeli)

sortowanie kończymy, gdy podczas kolejnego przejścia przez całą tabelę nie
wykonana zostanie żadna zamiana elementów

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

39/55

Sortowanie bąbelkowe

Sortowanie bąbelkowe -- przykład

przykład

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

40/55

Sortowanie bąbelkowe

Sortowanie bąbelkowe

Funkcja w języku C:

void BubbleSort(int tab[])

{

int i,j,tmp,koniec;

do

{

{

koniec=0;

for (i=0;i<N-1;i++)

if (tab[i]>tab[i+1])

{

tmp=tab[i];

tab[i]=tab[i+1];

tab[i+1]=tmp;

koniec=1;

}

}

while (koniec);

}

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

41/55

Sortowanie bąbelkowe

Sortowanie bąbelkowe

Uwagi

:

złożoność algorytmu:

O(n

2

)

+

prosta realizacja

+

wysoka efektywność użycia pamięci (sortowanie w miejscu)

+

wysoka efektywność użycia pamięci (sortowanie w miejscu)

+

stabilny algorytm - zachowuje oryginalną kolejność takich samych elementów

mała efektywność

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

42/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

algorytm opracowany przez C.A.R. Hoare’a

Algorytm metody

:

sortowanie odbywa się w dwu fazach:

dzielenia

i

sortowania

w fazie dzielenia tablica jest dzielona na dwie części wokół pewnego elementu
(nazywanego elementem centralnym)

(nazywanego elementem centralnym)

wybieramy jeden element (losowo, choć może to być element środkowy)
i nazywamy go

x

przeglądamy tablicę od lewej strony, aż znajdziemy element

a

i

x

, ≥a następnie

przeglądamy tablicę od prawej strony, aż znajdziemy

a

j

≤ x

zamieniamy elementy

a

i

i

a

j

miejscami i kontynuujemy proces przeglądania

i zamiany, aż nastąpi gdzieś spotkanie w środku tablicy

w rezultacie otrzymujemy tablicę podzieloną na lewą część z wartościami
mniejszymi od

x

i na prawą część z wartościami większymi od

x

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

43/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Algorytm metody (cd.)

:

na tym kończy się faza podziału i rozpoczyna faza sortowania

faza sortowania zawiera dwa rekurencyjne wywołania tej samej funkcji
sortowania: dla lewej i dla prawej części posortowanej tablicy

rekurencja zatrzymuje się, gdy wielkość tablicy do posortowania wynosi 1

rekurencja zatrzymuje się, gdy wielkość tablicy do posortowania wynosi 1

Przykład:

sortujemy 6-elementową tablicę

tab

:

wywołanie funkcji

QuickSort()

ma postać:

QuickSort(tab,0,5);

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

44/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Przykład: - dla QuickSort(tab,0,5):

wyznaczamy element środkowy:

(0+5)/2 = 2

,

x = tab[2] = 5

od lewej szukamy

tab[i]

x

, a od prawej

tab[j]

x

, zamieniamy elementy miejscami

poszukiwania kończymy, gdy indeksy
mijają się

wywołujemy rekurencyjnie funkcję

QuickSort()

dla elementów z zakresów

[l,j]

i

[i,r]

:

QuickSort(tab,0,3); QuickSort(tab,4,5);

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

45/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Przykład: - dla QuickSort(tab,0,3):

wyznaczamy element środkowy dla zakresu

[0,3]

:

(0+3)/2 = 1

,

x = tab[1] = 2

od lewej szukamy

tab[i]

x

,

a od prawej

tab[j]

x

, zamieniamy

elementy miejscami:

1

2

4

3

0

1

2

3

poszukiwania kończymy,
gdy indeksy mijają się:

wywołujemy rekurencyjnie funkcję

QuickSort()

tylko dla elementów z zakresu

[2,3]

,

gdyż po lewej stronie rozmiar tablicy do posortowania wynosi 1:

QuickSort(tab,2,3);

j

i

zamiana

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

46/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Przykład: - dla QuickSort(tab,2,3):

wyznaczamy element środkowy dla zakresu

[2,3]

:

(2+3)/2 = 2

,

x = tab[2] = 3

od lewej szukamy

tab[i]

x

,

a od prawej

tab[j]

x

,

zamieniamy elementy miejscami:

poszukiwania kończymy,
gdy indeksy mijają się:

rozmiar obu tablic do posortowania wynosi 1 więc nie ma nowych wywołań

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

47/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Przykład: - dla QuickSort(tab,4,5):

wyznaczamy element środkowy dla zakresu

[4,5]

:

(4+5)/2 = 4

,

x = tab[4] = 6

od lewej szukamy

tab[i]

x

,

a od prawej

tab[j]

x

,

zamieniamy elementy miejscami:

poszukiwania kończymy,
gdy indeksy mijają się:

rozmiar obu tablic do posortowania wynosi 1 więc nie ma nowych wywołań

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

48/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Funkcja w języku C:

void QuickSort(int tab[], int l, int r)

{

int i,j,x,y;

i=l;

j=r;

j=r;

x=tab[(l+r)/2];

do

{

while (tab[i]<x) i++;

while (x<tab[j]) j--;

if (i<=j)

{

y=tab[i];

tab[i]=tab[j];

tab[j]=y;

i++; j--;

}

} while (i<=j);

if (l<j) QuickSort(tab,l,j);

if (i<r) QuickSort(tab,i,r);

}

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

49/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Wybór elementu centralnego:

wybór elementu centralnego ma bardzo duży wpływ na szybkość sortowania

maksymalne korzyści są osiągane wtedy, gdy element centralny jest medianą
wszystkich wartości w tablicy - tablica dzielona jest w takim przypadku na dwie
równe części

wybrać można dowolny element, gdyż ważna jest jego wartość, a nie położenie
w tablicy

nie jest zalecane wybieranie elementu pierwszego lub ostatniego w tablicy,
gdyż w przypadku posortowanej tablicy taki wybór spowoduje największe
koszty

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

50/55

Sortowanie szybkie (Quick

Sortowanie szybkie (Quick--Sort)

Sort)

Uwagi

:

złożoność algorytmu:

O(n log n)

- dla średniego przypadku

O(n

2

)

- dla najgorszego przypadku

+

wysoka efektywność dla średniego przypadku

+

wysoka efektywność dla średniego przypadku

bardzo mała efektywność dla najgorszego przypadku

duże zasoby zajmowane w trakcie pracy (dużo danych na stosie)

niestabilny algorytm (nie zachowuje oryginalnej kolejności takich samych elementów)

ilość danych umieszczanych na stosie można nieznacznie zmniejszyć poprzez
przekazywanie do funkcji

QuickSort()

zamiast:

- tablicy danych, dolnego i górnego zakresu danych -

QuickSort(tab,left,right)

przekazać tylko:

- adres początku zaktualizowanej tablicy i całkowitą liczbę elementów, które

pozostały do posortowania w tej części tablicy -

QuickSort(tab,n)

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

51/55

Sortowanie szybkie

Sortowanie szybkie -- funkcja qsort() w języku C

funkcja qsort() w języku C

algorytm sortowania szybkiego został zaimplementowany w języku C w funkcji:

QSORT

stdlib.h

void qsort(void *baza, size_t n, size_t size,

(*funkcja)(const void *element1, const void *element2));

funkcja

qsort()

sortuje metodą Quick-Sort tablicę wskazywaną przez argument

baza

i zawierającą

n

elementów o rozmiarze

size

funkcja

qsort()

posługuje się funkcją porównującą

funkcja()

, której argumentami

są wskazania do elementów tablicy

baza

funkcja()

powinna zwracać wartości:

< 0

,

gdy

*element1 < *element2

== 0

,

gdy

*element1 == *element2

> 0

,

gdy

*element1 > *element2

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

52/55

Funkcja qsort() w języku C

Funkcja qsort() w języku C -- przykład (1/2)

przykład (1/2)

/* Name: w13_03_qsort.c

Copyright: Politechnika Białostocka, Wydział Elektryczny

Author: Jarosław Forenc (jarekf@pb.edu.pl)

Date: 06-06-2007

Description: Zastosowanie funkcji bibliotecznej qsort() */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <time.h>

#define N 10

void generuj(int tab[])

{

int i;

srand(time(NULL));

for (i=0;i<N;i++)

tab[i]=rand()%100;

}

void drukuj(int tab[])

{

int i;

for (i=0;i<N;i++)

printf("%2d ",tab[i]);

printf("\n");

}

background image

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

53/55

Funkcja qsort() w języku C

Funkcja qsort() w języku C -- przykład (2/2)

przykład (2/2)

int funkcja(const void *element1, const void *element2)

{

if (*(int*)element1 < *(int*)element2) return -1;

if (*(int*)element1 == *(int*)element2) return 0;

if (*(int*)element1 > *(int*)element2) return 1;

}

int main()

int main()

{

int tab[N];

generuj(tab);

drukuj(tab);

printf("\nqsort:\n");

qsort((void*)tab,(size_t)N,sizeof(int),funkcja);

drukuj(tab);

system("PAUSE");

return (0);

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

54/55

Funkcja qsort() w języku C

Funkcja qsort() w języku C -- przykład (2/2)

przykład (2/2)

int funkcja(const void *element1, const void *element2)

{

if (*(int*)element1 < *(int*)element2) return -1;

if (*(int*)element1 == *(int*)element2) return 0;

if (*(int*)element1 > *(int*)element2) return 1;

}

int main()

6

7

31

22

66

89

22

27

26

52

qsort:

6

7

22

22

26

27

31

52

66

89

int main()

{

int tab[N];

generuj(tab);

drukuj(tab);

printf("\nqsort:\n");

qsort((void*)tab,(size_t)N,sizeof(int),funkcja);

drukuj(tab);

system("PAUSE");

return (0);

}

Informatyka 2, studia niestacjonarne I stopnia

dr inż. Jarosław Forenc

Rok akademicki 2009/2010, Wykład nr 4

55/55

Koniec wykładu nr 4

Koniec wykładu nr 4

Dziękuję za uwagę!

Dziękuję za uwagę!

Dziękuję za uwagę!

Dziękuję za uwagę!


Wyszukiwarka

Podobne podstrony:
INF2 2009 Wykl 04 Zaoczne 4na1 Nieznany
INF2 2009 Wykl 04 Zaoczne 4na1 Nieznany
2008 patomorfologia wykl 04 wersja studencka
2009 05 04 Rozp MON używanie znaków w SZ RP
2009 03 04 POZ 01id 26786 ppt
wykl.04
Język jako narzedzie komunikacji wykł 9 04.12.07
2009-03-04, pedagogium, wykłady, Teoretyczne podstawy wychowania, ćwiczenia
HME 5sem Wykl Kostro Zaoczne All
Wykł L 04 Przyrządy i technologie półprzewodnikowe
INF1 2011 Wykl 07 Dzienne 4na1
Prawo budowlane wykł 5 04 13
2009.11.04 - WIELKIE JABŁKO NA MANHATTANIE, Z bryla.gazetadom.pl
MD wykl 04
2009.06.04 - Niesklasyfikowani, Testy, testy sędziowskie
04 Wykł 04 Dynamika bryły
2009 05 04 Rozp MON inne znaki używane w SZ RP
2009 05 04 ZAL
2009.11.04 - SIEDZIBA VITRY - ARCHITEKTONICZNA MEKKA, Z bryla.gazetadom.pl

więcej podobnych podstron