Řadící algoritmy

---

Verze z 31. 10. 2013, 12:31

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ů