Řadící algoritmy
Z MiS
(Rozdíly mezi verzemi)
(→Vlastnosti: Upřesnění pojmu Přirozený algoritmus) |
m (→Vlastnosti: U složitostí používáme velké N) |
||
| (Není zobrazena 1 mezilehlá verze od 1 uživatele.) | |||
| Řádka 15: | Řádka 15: | ||
== Vlastnosti == | == Vlastnosti == | ||
; Stabilita (''stable sorting'') | ; Stabilita (''stable sorting'') | ||
| − | * | + | * Algoritmus vždy zachová pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné). |
| − | + | <div class="Poznamka"> | |
| + | 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í. | ||
| + | </div> | ||
; Přirozenost (''natural, adaptive algorithm'') | ; Přirozenost (''natural, adaptive algorithm'') | ||
| − | * | + | * Algoritmus provede řazení rychleji (v menším počtu kroků), pokud je vstupní posloupnost již částečně seřazená. |
| − | + | <div class="Poznamka">Poznámky: | |
| − | + | # Mluvíme-li o zrychlení, myslíme tím zrychlení '''asymptotické'''.<br />''Tedy třeba to, že v „dobrých“ případech se dostaneme ze složitosti <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.<br />''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ý.'' | |
| + | </div> | ||
== Známé algoritmy == | == Známé algoritmy == | ||
Aktuální verze z 11. 12. 2014, 16:31
Ř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)
- Algoritmus vždy zachová pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné).
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)
- Algoritmus provede řazení rychleji (v menším počtu kroků), pokud je vstupní posloupnost již částečně seřazená.
Poznámky:
- 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. - 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
- 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ů
