ベストアンサー
まず、マージソートのように、漸近的に高速な代替案が存在するのに、なぜ二次ソートアルゴリズムを使用するのかを尋ねる必要があります。またはクイックソート。小さな配列（20〜30要素未満）の場合、挿入ソートと選択ソートはどちらも、通常、O（n * logn）の選択肢よりも高速です。実際、分割統治パラダイムに基づく多くのソートアルゴリズムは、配列が十分に小さい場合、挿入ソートまたは選択ソートに切り替わります。
挿入ソートと選択ソートの間で、どちらを使用するか？
通常、挿入ソートは、配列の「ソート」の程度に応じて、選択ソートよりも比較が少なくなります。選択ソートは要素を配置するときに配列の残りの部分をスキャンする必要がありますが、挿入ソートは必要な数の要素のみをスキャンします。つまり、配列がすでにソートされているか、ほぼソートされている場合、挿入ソートはO（n）時間で実行されます。
挿入ソートに対する選択ソートの利点の1つは、書き込み（スワップ）の数がO（n）、挿入ソートではO（n ^ 2）にあります。これは、たとえば、書き込みによってフラッシュメモリの寿命が短くなるため、フラッシュメモリで並べ替える場合に重要になることがあります。
回答
選択並べ替えでは、並べ替えられたセクションに追加するには、リストの全体の並べ替えられていない部分をスキャンして、残りの最小要素を見つける必要があります。挿入ソートでは、ソート済みセクションを検索して次の要素の場所を見つける必要がありますが、挿入ポイント（約半分）が見つかると検索は終了します。
したがって、選択ソートでは、各要素をソートセクションに追加するために平均でN / 2の比較が必要であり、挿入ソートでは平均でN / 4の比較が必要です。ただし、挿入ソートには、配列をソートするときに追加の時間ペナルティがあります。 N / 4（平均）の各比較では、要素を上にシフトする必要があるため、比較だけでなくN / 4の移動もあります。選択ソートは1回のスワップのみを必要とします。
全体として、挿入ソートは通常、競争に勝ちます。これは、（配列の場合）高速な「ブロック移動」機能がある場合に特に当てはまります。