Next: Přímé vkládání
Up: Sorting - třídění
Previous: Hledání polohy v tabulce
Seřazení
čísel podle velikosti - proces řádu složitosti
.
Zopakovat
-krát proces vyhledání intervalu přímo nelze.
Malý počet čísel lze seřadit i algoritmem řádu
s malou multiplikativní konstantou.
Ukážeme následující algoritmy
- Přímé vkládání - složitost

- Shellova metoda - složitost
(pro
náhodná čísla
)

- Heapsort - složitost
Názorný algoritmus, nepotřebuje žádnou paměť navíc.
Nejhorší případ je jen asi o 20 % pomalejší než průměrná rychlost.
- Quicksort - složitost
- nejhorší případ (pro
náhodná čísla
náhodná
- nejrychlejší známý - 1.5 až 2-krát
rychlejší než Heapsort. Ovšem v nejhorším případě (pro správně seřazená čísla) má
Quicksort složitost
.
Subsections
Jiri Limpouch
2000-03-29