標準選択ソートアルゴリズムの最良のシナリオは何でしょうか？

Question

要素を昇順または降順で並べ替えますか？

これは挿入ソートでも同じですか？

Answer 1

選択ソートの場合、最良のケースは既に注文されているアイテムです。しかし、これは実行時間を大幅に改善するものではありません。選択ソートには早期終了条件はありません。リストがすでに整っているかどうかにかかわらず、すべてのアイテムをチェックする必要があります。それは常に（n^2 - n）/ 2の比較をします。事前ソートされたリストを持つ唯一のことは、n "スワップ"操作の必要性を排除することです。

挿入ソートの場合は、あらかじめソートされたリストもあります。その場合、挿入ソートはO（n）で実行されます。降順は挿入ソートの最悪のケースです。