Řadící algoritmy

Z MiS
(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
(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'')
* Pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné), zůstane zachované.
+
* Algoritmus vždy zachová pořadí prvků, které mají stejnou hodnotu v rámci uspořádání (jsou stejné).
* Můžeme pak řadit podle více kritérií postupně.
+
<div class="Poznamka">
 +
U&nbsp;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'')
* Pokud je vstupní posloupnost již částečně seřazená, je řazení rychlejší.
+
* Algoritmus provede řazení rychleji (v&nbsp;menším počtu kroků), pokud je vstupní posloupnost již částečně seřazená.
* Myslí se tím zrychlení ''asymptotické''.
+
<div class="Poznamka">Poznámky:
*: Tedy třeba že v&nbsp;„dobrých“ případech se dostaneme z&nbsp;<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 (s&nbsp;mírou seřazenosti vstupu).
+
# 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>
  
 
== 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)

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