SelectionSortとInsertionSort

Question

私は次の質問に答える必要があります。InsertSortよりもSelectionSortが良い（結果の開発に関して）シナリオを考えてください。

私の考えは、あなただけが必要な場合です。非常に大きなリストのトップ10、あなたは10番目のステップの後でソートを終了することができます。これはこの質問に対する有効な答えですか？他のシナリオを考えてもらえますか？

Answer 1

入力配列が「ソート済み」に近い場合、ソートソートは挿入ソートよりもパフォーマンスが優れています。選択ソートにはΘ（n）スワップとΟ（n2）（挿入ソートの場合）のみが必要です。選択ソートには安定性が強く実現されています。

Answer 2

最悪の場合、InsertSortのスワップはΟ(n^2)ですが、SelectionSortはΘ(n)です。したがって、書き込みが読み取りよりも大幅に高価な場合は、SelectionSortが適しています。