Triedenie
Triedenie.
- je proces preusporiadania danej mnoziny objektov v specifickom
poradi. Ucel: ulahcit vyhladavanie urc. prvku.
Rozlisujeme metody triedenia a) poli ( tzv. vnutorne tried. )
b) suborov ( tzv. vonkajsie rtied.)
Triedenie poli.
a) triedenie vkladanim
b) triedenie vyberom
c) triedenie vymenou
Priame metody triedenia.
Priame triedenia su charakteristicke tym,ze su vhodne na
objasnenie charakteristickych crt triedenia.Ich programy su lahko
pochopitelne a kratke,maju malu pametovu narocnost.Pre maly pocet
prvkov je ich casova narocnost porovnatelna s algoritmami s
logaritmickou casovou narocnostou.
Triedenie vkladanim.
Pr. Majme postupnost prvkov, ktore mame usporiadat podla velkosti
od najmensieho po najvecsie.
44 55 12 42 94 18 06 67
Trieto udaje ulozime do pola a[1], ... a[n]
Algoritmus: Pre i= 2 po n
vkladame a[i]-ty prvok na prislusne miesto v
postupnosti prvkov a[1],.....a[i]
ÚÄÄż
44 ł55ł 12 42 94 18 06 67
ŔÄÄŮÚÄÄż
44 55 ł12ł 42 94 18 06 67
ŔÄÄŮÚÄÄż
12 44 55 ł42ł 94 18 06 67
ŔÄÄŮÚÄÄż
12 42 44 45 ł94ł 18 06 67
ŔÄÄŮÚÄÄż
12 42 44 45 94 ł18ł 06 67
ŔÄÄŮÚÄÄż
12 18 42 44 45 94 ł06ł 67
ŔÄÄŮÚÄÄż
06 12 18 42 44 45 94 ł67ł
ŔÄÄŮ
06 12 18 42 44 45 67 94
Triedenie vyberom
Metoda triedenia vyberom je jednou z najzakladnejsich druhov
triedenia pola.Algoritmus je zalozeny na nasledujucom principe -
- Zo vsetkych prvkov pola sa vyberie najmensi prvok a tento sa
vymeni s 1. prvkom. Zo zostavajucej casti pola sa opet vyberie
najmensi prvok a vymeni sa s 2. prvkom.proces sa opakuje az kym
nie je cele pole utriedene.
Bublinkove triedenie.
Tato metoda sa niekedy nazyva Triedenie priamou vymenou, pretoze
tato metoda je charakteristicka tym, ze vymena dvoch prvkov je
dominantnou operaciou.Algoritmus je zalozeny na principe
postupneho porovnavania a vymeny dvoch susednych prvkov.V ramci
kazdeho prechodu polom sa najvecsi prvok posunie na horny okraj
pola. Ak by sme si prvky predstavili ako bubliny vo vodnej nadrzi
,tak v ramci kazdeho prechodu dojde k "prebublaniu" prvku na
uroven zodpovedajucu jeho velkosti. .
|
