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)
  • nemusí byť relácia usporiadania
• 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é

• Vlastnosti algoritmov řazení:
  • sekvenčnosť = algoritmus pristupuje k prvkom sekvenčne (opakom je priamy(náhodný) prístup)
  • prirodzenosť = doba seřazení opačne usporiadaného poľa > náhodne usporiadaného poľa > usporiadaného poľa (inak sa nechová prirodzene)
  • stabilita = algoritmus zachováva relatívne poradie kľúčov s rovnakou hodnotou
  • in situ = pracujú na „mieste samom“ - nepotrebujú žiadnu pamäť navyše

• Řazení podľa viacerých kľúčov:
  • 3 spôsoby riešenia:
    • vytvorenie zloženej relácie usporiadania (funkcia pre porovnávanie vráti jednoznačne, najprv porovná rok, potom mesiac, nakoniec deň)
    • podľa vzrastajúcej priority kľúčov (najprv deň, potom mesiac, potom rok) - je nutné použiť stabilnú metódu řazení
    • aglomerovaný kľúč - usporiadaná N-tica kľúčov sa konvertuje na vhodný typ, nad ktorým je definovaná relácia usporiadania (napr. dátum narodenia môžme prekonvertovať na číslo RRMMDDXXXX)

• Řazení bez presunu položiek
  • v prípade „dlhých“ položiek sú presuny dosť náročná operácia
  • pomocné pole (poradník) - určuje indexy prvkov
  • pri řazení nevymieňam položky, ale indexy v poradníku
  • používajú sa nepriame adresy (pole[pomocnePole[i]])
  • zreťazenie prvkov - pomocou ukazateľov
  • MacLarenov algoritmus - netreba vedieť kód, ale treba vedieť nakresliť a vysvetliť princíp, pracuje in situ!!!
    1. první prvek seznamu (na který ukazuje proměnná Prvni) se vymění s prvkem pole na indexu 1.
    2. tím se nejmenší položka dostane na své místo
    3. na prvek, který byl z prvního indexu pole odsunut jinam však některý prvek ukazoval, je třeba ho najít a změnit jeho ukazatel tak, aby místo na první index ukazoval na místo, kam byl první odsunut
    4. tím je první prvek ošetřen. Dalším „prvním“ se stane index o jednu větším a cyklus pokračuje tak dlouho, až se vymění předposlední (Max-1) prvek, kdy cyklus končí
    5. s ohledem na velkou délku položky je součet času řadicího algoritmu bez přesunu položek (minimálně linearitmický) s časem McLarenova algoritmu (lineární) kratší, než čas samotného řadicího algoritmu s přesunem položek

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ě
}    

• a ešte jedno vysvetlenie:
  • Algoritmus pracuje s původním polem, jehož položky jsou zřetězené do seřazeného seznamu. Umístí se první položka na své místo a upraví se ukazatel v položce, který na ni ukazoval. Stejným způsobem se přesune druhá položka na své místo… Takhle se projde celým seznamem.

• 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:
    • sériové
    • paralelné
  • 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