Nejlepší odpověď
Nejprve by se mělo zeptat, proč použít kvadratický třídicí algoritmus, když existují asymptoticky rychlejší alternativy, jako je mergesort nebo quicksort. U malých polí (méně než 20–30 prvků) je jak řazení, tak výběrové řazení obvykle rychlejší než alternativy O (n * logn). Ve skutečnosti mnoho algoritmů řazení založených na paradigmatu rozděl a panuj přepne na třídění vložení nebo výběr, když je pole dostatečně malé.
Mezi vložením a výběrem řazení, kdy použít který?
Třídění vložení obvykle provede menší srovnání než výběrové řazení, v závislosti na stupni „seřazenosti“ pole. Zatímco řazení výběru musí při umisťování prvku skenovat zbývající části pole, třídění vkládání skenuje pouze tolik prvků, kolik je potřeba. To znamená, že když je pole již tříděno nebo téměř tříděno, třídění vkládání probíhá v čase O (n).
Jednou z výhod řazení řazení oproti řazení je, že počet zápisů (swapů) je v O (n), zatímco ve vloženém řazení je v O (n ^ 2). To může být důležité například při třídění na paměti Flash, protože zápisy zkracují životnost paměti Flash.
Odpovědět
Ve výběru se pro každý prvek, který má být Chcete-li přidat do seřazené sekce, musíte naskenovat celou netříděnou část seznamu, abyste našli minimální zbývající prvek. Při třídění vložení musíte prohledat sekci seřazeno , abyste zjistili, kam jde další prvek, ale hledání končí, jakmile najdete bod vložení (přibližně polovina cesta tříděnou sekcí v průměru).
Takže výběr řazení vyžaduje průměrné N / 2 srovnání pro každý prvek, který má být přidán do seřazené sekce a třídění vložení vyžaduje N / 4 srovnání průměrně. Třídění vložení má však při řazení pole další časovou penalizaci. Každé z N / 4 (v průměru) srovnání vyžaduje, aby byl prvek posunut nahoru, takže existují i N / 4 tahy a srovnání. Třídění výběru vyžaduje pouze jeden swap.
Celkově řazení obvykle vyhraje závod. To platí zejména v případě, že jsou v okolí rychlé funkce „blokování pohybu“ (pro pole).