挿入ソートと選択ソートの違いを理解しようとしています。
どちらも、ソートされていないサブリストとソートされたサブリストという 2 つのコンポーネントがあるようです。どちらも、ソートされていないサブリストから 1 つの要素を取り出して、ソートされたリストの適切な場所に配置するようです。選択ソートは、一度に 1 組の要素を交換することによってこれを実行し、挿入ソートは単に適切な場所を見つけて挿入すると述べているサイトや書籍をいくつか見ました。ただし、挿入ソートも交換すると述べている記事も見ました。そのため、混乱しています。標準的なソースはありますか?
ベストアンサー1
選択ソート:
リストが与えられた場合、現在の要素を取得し、それを現在の要素の右側にある最小の要素と交換します。
挿入ソート:
リストが与えられたら、現在の要素を取得してリストの適切な位置に挿入し、挿入するたびにリストを調整します。これは、カード ゲームでカードを並べるのと似ています。
選択ソートの時間計算量は常に ですn(n - 1)/2が、挿入ソートの時間計算量は最悪の場合の計算量が であるため、よりn(n - 1)/2少なくなります。一般に、その場合、 より少ないか等しい比較が必要になりますn(n - 1)/2。
ソース：http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html