Základné algoritmy

Programovanie - prednáška

č.3

1

Základné algoritmy

OBSAH

1.

Riešenie numerických úloh
•

h

ľadanie minima, maxima, priemeru

•

práca s maticami

2.

Triedenie
•

priamym vkladaním

•

priamym výberom

•

priamou výmenou (bublinové triedenie)

3.

Vyh

ľadávanie

•

binárne vyh

ľadávanie

Programovanie - prednáška

č.3

2

•

Hľadanie minima

•

Hľadanie maxima

•

Výpočet priemeru

•

Práca s maticami

Základné algoritmy –

riešenie numerických úloh

Programovanie - prednáška

č.3

3

•

Def.: Proces preusporiadania danej množiny objektov v
špecifickom poradí.

•

Účelom triedenia je uľahčiť neskoršie vyhľadávanie
prvkov triedenej množiny.

•

Dôležitá a základná činnosť v spracovaní údajov (objekty
sa triedia v telefónnych zoznamoch, registroch daní z
príjmu, obsahoch kníh, knižniciach, slovníkoch,...)

•

Veľká závislosť výberu algoritmu od štruktúry údajov ⇒
obvyklé základné delenie na:
•

Triedenie polí (vnútorné triedenie – polia sa uchovávajú
vo vnútorných pamätiach počítačov)

•

Triedenie (sekvenčných) súborov (vonkajšie triedenie –
súbory sú umiestnené na väčších a pomalších vonkajších
pamäťových médiách – disky/pásky)

Triedenie

Programovanie - prednáška

č.3

4

•

Máme prvky: a

1, a2, ..., an

•

Triedenie s počíva v permutovaní týchto prvkov na také
poradie: a

k1, ak2, ..., akn,

že ak je daná funkcia usporiadania f, platí:

f(a

k1) ≤ f(ak2) ≤ ... ≤ f(akn)

•

Zvyčajne sa funkcia usporiadania nevyhodnocuje podľa
špecifikovaného pravidla výpočtu, ale je uložená ako explicitná
zložka (časť) každého prvku = kľúč

•

Na zobrazenie prvkov

a

i sa teda mimoriadne hodí štruktúra

záznamu pozostávajúca z kľúča (napr. typu celé číslo s
predpokladaným úmyslom identifikovať prvky) a zvyšných
zložiek (pre účely triedenia nepodstatné)

•

Meradlo efektívnosti metód triedenia: počet porovnaní kľúčov
(C) + počet presunov prvkov (M)

Triedenie – pojmy a zápis

Programovanie - prednáška

č.3

5

Dôvody použitia:
1. Vhodné na objasnenie charakteristických čŕt hlavných zásad

triedenia.

2. Ich programy sú ľahko pochopiteľné a krátke.
3. Rýchlejšie pre dostatočne malé n, nepoužívajú sa však pre

veľké n.

Rozdelenie na kategórie:
1. Triedenie vkladaním.
2. Triedenie výberom.
3. Triedenie výmenou.

Triedenie polí - priame

metódy

Programovanie - prednáška

č.3

6

•

Prvky sa rozdelia na dve skupiny: zdrojovú (

a

i, ..., an) a

cieľovú (

a

1, ..., ai-1)

•

V rámci každého kroku algoritmu sa zo zdrojovej postupnosti
vyberie i-ty prvok a vloží sa na patričné miesto cieľovej
postupnosti

•

viď vývojový diagram

•

C

min = n – 1; Cmax =

C

priem =

•

M

min = 2(n – 1); Mmax =

M

priem =

Triedenie priamym

vkladaním

∑

∑

−

=

=

−

=

−

=

=

−

1

1

2

2

2

/

)

(

2

/

)

1

(

*

)

1

(

n

i

n

i

n

n

n

n

i

i

4

/

)

2

(

2

/

)

1

2

/

)

1

(

(

2

/

2

2

−

+

=

−

+

=

∑

=

n

n

n

n

i

n

i

2

/

)

2

(

)

1

2

/

)

1

(

(

2

2

−

+

=

−

+

=

∑

=

n

n

n

n

i

n

i

4

/

)

6

5

(

1

2

/

1

4

/

)

1

(

)

1

2

/

(

2

2

−

+

=

−

+

−

+

=

+

∑

=

n

n

n

n

n

i

n

i

Programovanie - prednáška

č.3

7

1. Vyber prvok s najmenším kľúčom.
2. Vymeň ho s prvým prvkom a

1.

3. Opakuj postupne s n-1 prvkami, n-2 prvkami,... Až ostane

jediný najväčší prvok.

•

viď vývojový diagram

•

C =

M

min = 3(n-1); Mmax =

M

priem =

•

Vo všeobecnosti je toto triedenie efektívnejšie ako triedenie
priamym vkladaním (až na postupnosti usporiadané resp.
takmer usporiadané)

Triedenie priamym výberom

)

(ln

γ

+

n

n

)

1

(

3

4

2

−

+













n

n

trunc

...

577216

,

0

.

=

γ

konšt

Eulerova

2

/

)

(

2

n

n

−

Programovanie - prednáška

č.3

8

•

tzv. bublinové triedenie – postupné porovnávanie a zámena
susedných dvojíc, až kým nie je pole utriedené

•

viď vývojový diagram

•

C =

M

min = 0; Mmax =

M

priem =

•

Vo všeobecnosti je toto triedenie najmenej efektívne z
uvádzaných algoritmov triedenia

Triedenie priamou výmenou

)

(

2

3

2

n

n

−

2

/

)

(

2

n

n

−

)

(

4

3

2

n

n

−

Programovanie - prednáška

č.3

9

Iné algoritmy vnútorného

triedenia

•

Triedenie vkladaním so zmenšovaním kroku (Shellovo
triedenie)

•

Stromové triedenie (bude uvedené neskôr pri dynamických
údajových štruktúrach)

•

Vylepšené triedenie výmenou – rýchle triedenie (quicksort) –
najlepšia metóda triedenia v poli (bude uvedená neskôr pri
preberaní rekurzie)

Programovanie - prednáška

č.3

10

Vyh

ľadávanie

•

Nájdenie prvku poľa (napr. min, max, zadaného prvku) – v
neusporiadanom poli – viď príklady z úvodu prednášky

•

Vyhľadávanie sa dá podstatne urýchliť, ak sú prvky poľa
usporiadané ⇒ najzaužívanejšou technikou je opakované
delenie intervalu na podintervaly, v ktorých sa hľadaný prvok
hľadá ⇒ binárne vyhľadávanie

•

viď vývojový diagram