挿入ソートと選択ソートの違いを理解しようとしています。
どちらも、ソートされていないリストとソートされたリストの 2 つのコンポーネントを持っているようです。どちらも、ソートされていないリストから1つの要素を取得し、それをソートされたリストの適切な場所に配置しているようです。選択ソートは一度に1つずつ交換することでこれを行うのに対し、挿入ソートは単に適切な場所を見つけて挿入すると言っているサイト/本を見たことがあります。ただし、他の記事で、挿入ソートもスワップされると述べているのを見たことがあります。その結果、私は混乱しています。正規のソースはありますか？
挿入ソートと選択ソートの両方に、外側のループ (すべてのインデックスに対する) と内側のループ (インデックスのサブセットに対する) があります。内側のループの各パスは、ソートされていない要素がなくなるまで、ソートされていない領域を犠牲にして、ソートされた領域を 1 要素ずつ拡張します。
違いは、内側のループが行うことです。
選択ソートでは、内側のループはソートされていない要素です。各パスは 1 つの要素を選択し、それを最終的な場所 (並べ替えられた領域の現在の端) に移動します。
挿入ソートでは、内側のループの各パスがソートされた要素を反復処理します。並べ替えられた要素は、ループが次の並べ替えられていない要素を挿入する正しい場所を見つけるまで置き換えられます。
そのため、選択ソートでは、ソートされた要素は出力順に検出され、検出された後はその位置にとどまります。逆に、挿入ソートでは、ソートされていない要素は入力順に消費されるまで配置されたままになりますが、ソートされた領域の要素は移動し続けます。
スワッピングに関する限り、選択ソートは内部ループのパスごとに 1 つのスワップを行います。挿入ソートは通常、内側のループのtemp 前に挿入される要素を保存し、内側のループがソートされた要素を 1 つ上にシフトする余地を残し、temp後で挿入ポイントにコピーします。
両方のアルゴリズムは通常、次のように機能します
ステップ1：ソートされていないリストから次のソートされていない要素を取得し、次に
ステップ 2: ソートされたリストの適切な場所に配置します。
ステップの 1 つは 1 つのアルゴリズムにとってより簡単であり、その逆も同様です。
挿入ソート: ソートされていないリストの最初の要素を取得し、ソート済みリストのどこかに配置します。次の要素 (ソートされていないリストの最初の位置) を取得する場所はわかっていますが、それを配置する場所 (どこか) を見つけるにはいくつかの作業が必要です。ステップ 1 は簡単です。
選択ソート: ソートされていないリストから要素を取得し、ソートされたリストの最後の位置に配置します。次の要素を見つけて (ソートされていないリストの最初の位置ではなく、どこかにある可能性が高い)、ソートされたリストの最後に配置する必要があります。ステップ2は簡単
一言で言えば、選択ソートは最初に配列内の最小値を検索してからスワップを行うのに対し、挿入ソートは値を取り、それをその後ろにある各値と比較すると思います。値が小さい場合、スワップします。次に、同じ値を再度比較し、後ろの値よりも小さい場合は、再度スワップします。それが理にかなっていることを願っています！
もう 1 度試してみましょう: ほとんど並べ替えられた配列の幸運なケースで何が起こるかを考えてみましょう。
並べ替え中、配列には 2 つの部分があると考えることができます: 左側 - 並べ替え済み、右側 - 並べ替えなし。
挿入並べ替え - 最初の並べ替えられていない要素を選択し、既に並べ替えられた部分の中からその場所を見つけようとします。右から左に検索するため、比較対象の最初のソート済み要素 (最大のもの、左部分の右端) が選択した要素よりも小さい可能性が非常に高く、次のソートされていない要素をすぐに続行できます。
選択ソート - 最初のソートされていない要素を選択し、ソートされていない部分全体の中で最小の要素を見つけようとし、必要に応じてそれら 2 つを交換します。問題は、正しい部分がソートされていないため、選択した要素よりも小さい要素があるかどうかを確認できないため、毎回すべての要素を考えなければならないことです。
ところで、これはまさにheapsortが選択ソートで改善されるものです。 heapにより、最小の要素をより迅速に見つけることができます。
選択ソート: ソートされたサブリストの構築を開始すると、アルゴリズムは、ソートされたサブリストが常に完全にソートされるようにします。これは、それ自体の要素だけでなく、完全な配列、つまりソートされたサブリストとソートされていないサブリストの両方に関してもソートされます。したがって、ソートされていないサブリストから見つかった新しい最小要素は、ソートされたサブリストの最後に追加されます。
挿入ソート: アルゴリズムは再び配列を 2 つの部分に分割しますが、ここでは要素が 2 番目の部分から選択され、最初の部分の正しい位置に挿入されます。もちろん、最終パスではすべての要素が正しいソート位置にあるにもかかわらず、これは最初の部分が完全な配列に関してソートされることを保証するものではありません。
基本的に、挿入ソートは一度に2つの要素を比較することで機能し、選択ソートは配列全体から最小の要素を選択してソートします。
概念的には、挿入ソートは配列全体がソートされるまで 2 つの要素を比較してサブリストをソートし続けますが、選択ソートは最小要素を選択し、最初の位置に 2 番目の最小要素を 2 番目の位置にスワップします。
挿入ソートは次のように表示できます。
for(i=1;i<n;i++)
for(j=i;j>0;j--)
if(arr[j]<arr[j-1])
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
選択ソートは次のように表示できます。
for(i=0;i<n;i++)
min=i;
for(j=i+1;j<n;j++)
if(arr[j]<arr[min])
min=j;
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
簡単な説明は次のようになります。
与えられた : 番号の並べ替えられていない配列またはリスト。
問題文: 選択ソートと挿入ソートの違いを理解するために、数値のリスト/配列を昇順にソートします。
挿入ソート:わかりやすいように、上から下にリストを表示します。最初の要素を最初の最小値と見なします。ここで、そのリスト/配列の各インデックスを直線的にトラバースして、最初の最小値よりも小さい値を持つ他の要素がインデックスにあるかどうかを調べるという考え方です。そのような値が見つかった場合は、それらのインデックスで値を交換するだけです。つまり、15 がインデックス 1 の最小初期値であり、インデックスの線形トラバーサル中に、より小さい値の数値に遭遇します。たとえば、インデックス 9 で 7 です。 . ここで、インデックス 9 のこの値 7 は、値として 15 を持つインデックス 1 と交換されます。このトラバーサルは、現在のインデックスの値と残りのインデックスの値との比較を続けて、より小さい値に交換します。これは、リスト/配列の最後の 2 番目のインデックスまで続きます。
選択ソート:リスト/配列の最初のインデックス要素がソートされていると仮定しましょう。次に、2 番目のインデックスの要素から、それを前のインデックスと比較して、値が小さいかどうかを確認します。走査は、ソート済みと未ソートの 2 つの部分に視覚化できます。リスト/配列内の特定のインデックスに対して、ソートされていないものからソートされているものへの比較チェックを視覚化することができます。インデックス 1 に値 19 があり、インデックス 3 に値 10 があるとします。ソートされていないものからソートされているもの、つまり右から左へのトラバーサルを考えます。したがって、インデックス 3 でソートする必要があるとしましょう。右から左に比較すると、インデックス 1 よりも値が小さいことがわかります。識別したら、インデックス 3 のこの数値 10 を、値 19 を持つインデックス 1 の場所に配置します。インデックス 1 の元の値 19 は、1 つ右にシフトされます。
質問はトラバーサルの方法の概念を理解することに関するように思われるため、コードを追加していません。
挿入ソートは、その選択をより多くスワップします。次に例を示します。
両方に共通しているのは、パーティションを使用して、配列のソートされた部分とソートされていない部分を区別することです。
違いは、選択ソートを使用すると、ソートされたパーティションに要素を追加するときに、配列のソートされた部分が変更されないことが保証されることです。
その理由は、選択によってソートされていないセットの最小値が検索され、ソートされたセットの最後の要素の直後に追加されるため、ソートされたセットが 1 増加するためです。
一方、挿入は、配列のソートされていない部分の最初の要素である、次に遭遇する要素だけを気にします。この要素を取得し、ソートされたセット内の適切な場所に単純に適合させます。
挿入ソートは通常、部分的にしかソートされていない配列の場合に適しています。これは、最小値を見つけるための操作が無駄になるためです。
結論：
選択ソートは、ソートされていないセクションで最小要素を見つけることにより、要素を最後に段階的に追加します。
挿入ソートは、ソートされていないセクションで見つかった最初の要素を、ソートされたセクションの任意の場所に伝播します。