Řadící algoritmy

Z MiS
Verze z 11. 12. 2014, 16:31; Spravce (diskuse | příspěvky)
(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání


Řadicí algoritmy jsou hezkou a tradiční ukázkou jednoduchých algoritmů. Učíme se je, abychom:

  • si pocvičili práci s kolekcemi, podmínky a cykly,
  • prakticky si ukázali složitost a vlastnosti algoritmů,
  • uvědomili si, že je třeba vybírat vhodný algoritmus pro danou úlohu.

Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě:

Collection.sort(seznam);

Viz také: Java: Řazení.

Obsah

Vlastnosti

Stabilita (stable sorting)

U stabilních řadících algoritmů můžeme řadit podle více kritérií tak, že postupně aplikujeme řazení pomocí jednotlivých kritérií.

Přirozenost (natural, adaptive algorithm)
Poznámky:
  1. Mluvíme-li o zrychlení, myslíme tím zrychlení asymptotické.
    Tedy třeba to, že v „dobrých“ případech se dostaneme ze složitosti O(N2) na O(N) apod.
  2. Počet operací by měl klesat postupně s počtem a velikostí seřazených bloků ve vstupní posloupnosti.
    Pokud například k algoritmu, který není přirozený, pouze předřadíme test, zda už posloupnost náhodou není seřazená na vstupu, stále výsledný algoritmus nebudeme považovat za přirozený.

Známé algoritmy

Související stránky

Zdroje

Osobní nástroje
Jmenné prostory
Varianty
Akce
Výuka
Navigace
Nástroje