Řadící algoritmy
Z MiS
(Rozdíly mezi verzemi)
m (Oprava odkazu) |
(→Vlastnosti: Upřesnění pojmu Přirozený algoritmus) |
||
| Řádka 14: | Řádka 14: | ||
== Vlastnosti == | == Vlastnosti == | ||
| − | ; Stabilita (stable sorting) | + | ; Stabilita (''stable sorting'') |
* Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované. | * Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované. | ||
* Můžeme pak řadit podle více kritérií postupně. | * Můžeme pak řadit podle více kritérií postupně. | ||
| − | ; Přirozenost | + | ; Přirozenost (''natural, adaptive algorithm'') |
* Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší. | * Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší. | ||
| + | * Myslí se tím zrychlení ''asymptotické''. | ||
| + | *: Tedy třeba že v „dobrých“ případech se dostaneme z <tt>O(n<sup>2</sup>)</tt> na <tt>O(n)</tt> apod. | ||
| + | * Počet operací by měl klesat ''postupně'' s počtem a velikostí seřazených bloků ve vstupní posloupnosti (s mírou seřazenosti vstupu). | ||
== Známé algoritmy == | == Známé algoritmy == | ||
Verze z 11. 12. 2014, 10:40
Ř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)
- Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované.
- Můžeme pak řadit podle více kritérií postupně.
- Přirozenost (natural, adaptive algorithm)
- Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší.
- Myslí se tím zrychlení asymptotické.
- Tedy třeba že v „dobrých“ případech se dostaneme z O(n2) na O(n) apod.
- Počet operací by měl klesat postupně s počtem a velikostí seřazených bloků ve vstupní posloupnosti (s mírou seřazenosti vstupu).
Známé algoritmy
- Insertion-sort
- Začínáme od prvního prvku, který tvoří „jednoprvkovou seřazenou posloupnost“.
- Postupně bereme další prvky a v každém kroku jeden prvek vložíme do seřazené posloupnosti, která se tak prodlouží.
- Shell-sort
- Simulace vyhledávacího stromu v poli
- Quick-sort
- Vybere „pivot“ („prostřední prvek“)
- Rozdělí prvky na ty, co jsou menší, a na ty, co jsou větší než pivot.
- Pak postupuje stejně v levé a pravé části.
- Merge-sort
- Spojuje dílčí seřazené posloupnosti do delších.
- „Opačný postup“ než u Quick-sortu (od spodu nahoru).
Související stránky
Zdroje
- Mnohem více informací získáte na:Algoritmy.net → Porovnání algoritmů
