Řadící algoritmy
Z MiS
(Rozdíly mezi verzemi)
(Vytvoření stránky) |
(Přidána poznámka, že existuje Collection.sort(...)) |
||
| Řádka 1: | Řádka 1: | ||
[[Category:VSE]][[Category:Informatika]][[Category:Programování]][[Category:Algoritmizace]] | [[Category:VSE]][[Category:Informatika]][[Category:Programování]][[Category:Algoritmizace]] | ||
| + | |||
| + | <div class="Poznamka"> | ||
| + | Ř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. | ||
| + | </div> | ||
| + | <div class="Varovani"> | ||
| + | Pokud ale opravdu potřebujete jen něco seřadit, použijte knihovny vašeho prog. jazyka! Například v Javě: | ||
| + | Collection.sort(seznam); | ||
| + | </div> | ||
== Vlastnosti == | == Vlastnosti == | ||
Verze z 18. 11. 2013, 09:35
Ř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);
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
- Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší.
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).
Zdroje
- Mnohem více informací získáte na:Algoritmy.net → Porovnání algoritmů
