27d - Řazení
účel řazení - uľahčenie vyhľadávania
algoritmy sú principiálne dvojcyklové
kvadratické a linearitmické zložitosti
řazení podľa viacerých kľúčov - najprv podľa kľúčov s menšou prioritou (jednotky - desiatky - stovky)
2 operácie, ktoré sa vykonávajú - porovnávanie a presun (presun je zpravidla časovo náročnejší)
Triedenie = usporiadanie položiek množiny podľa hodnoty daného atribútu (kľúča položky)
Usporiadanie = je zoradenie položiek podľa usporiadanej množiny kľúčov
Řazení = usporiadanie položiek podľa relácie lineárneho usporiadania na kľúči
Zlučovanie = vytváranie súboru položiek zjednotením niekoľkých súborov položiek rovnakého typu (niečo ako konkatenácia pri reťazcoch)
Setřídění (merging) = vytváranie súboru zoradených položiek zjednotením niekoľkých súborov položiek rovnakého typu, ktoré sú už zoradené
i:=1;
Pom := Prvni;
while (i < Max)
{
//Hledání následníka přesunutého na pozici větší než i
while (Pom < i)
{
//výměna akt. prvního s akt. minimálním
Pom = Pole[Pome].Uk;
}
Pole[i] = Pole[Pome;
Pole[i].Uk = Pom; //stejná výměna ukazatelů
i = i + 1; //prvních i-1 prvků je již na svém místě
}
Klasifikácia algoritmov:
Podľa prístupu k pamäti:
metódy vnútorného řazení - náhodný prístup (řazení polí)
metódy vonkajšieho řazení - sekvenčný prístup (řazení súborov, zoznamov)
Podľa typu procesoru:
Podľa prinícpu řazení:
princíp výberu (selection) - presúvajú max/min do výslednej postupnosti
princíp vkladania (insertion) - vkladajú postupne prvky do výslednej postupnosti
rozdeľovanie (partition) - rozeľuje postupne množinu prvkov na dve podmnožiny tak, že v jednej sú menšie prvky ako v druhej
zlučovanie (merging) - zotrieďuje postupne 2 zoradené podmnožiny do jednej