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