Řadící algoritmy

Z MiS

(Rozdíly mezi verzemi)

Přejít na: navigace, hledání

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:

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

Collection.sort(seznam);

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í.

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(N²) 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ý.

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).

@@ Řádka 23: / Řádka 23: @@
 * Algoritmus provede řazení rychleji (v&nbsp;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&nbsp;„dobrých“ případech se dostaneme ze složitosti <tt>O(n<sup>2</sup>)</tt> na <tt>O(n)</tt> apod.''
+# Mluvíme-li o zrychlení, myslíme tím zrychlení '''asymptotické'''.<br />''Tedy třeba to, že v&nbsp;„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&nbsp;počtem a&nbsp;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>