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
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
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)
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
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;
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):
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
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;
}
}
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
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);
}
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);
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);
}
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");
}
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ę!