insertion sort c with examples
古典的な例を使用した挿入ソートの詳細。
挿入ソートは、手元のカードをプレイする方法で表示できるソート手法です。カードをデッキに挿入したり取り外したりする方法、挿入ソートは同じように機能します。
挿入ソートアルゴリズムの手法は、バブルソートや選択ソートの手法よりも効率的ですが、クイックソートやマージソートなどの他の手法よりも効率的ではありません。
=> ここで最高のC ++トレーニングチュートリアルをチェックしてください。
学習内容：
概要概要
挿入ソート手法では、2番目の要素から始めて、最初の要素と比較し、適切な場所に配置します。次に、後続の要素に対してこのプロセスを実行します。
各要素を以前のすべての要素と比較し、要素を適切な位置に配置または挿入します。挿入ソート手法は、要素数が少ない配列の方が適しています。リンクリストの並べ替えにも役立ちます。
Javaで二重リンクリストを作成する方法
リンクリストには、次の要素へのポインタ（単一リンクリストの場合）と前の要素へのポインタ（二重リンクリストの場合）があります。したがって、リンクリストの挿入ソートの実装が容易になります。
このチュートリアルでは、挿入ソートについてすべて調べてみましょう。
一般的なアルゴリズム
ステップ1 ：K = 1〜N-1について、手順2〜5を繰り返します。
ステップ2 ：設定温度= A (K)
ステップ3 ：J = K –1に設定
ステップ4 ：一時的に繰り返す<=A(J)
セットA (J + 1) = A (J)
J = J –1に設定します
【インナーループ終了】
ステップ5 ：set A (J + 1) = temp
(ループの終わり)
ステップ6 ： 出口
したがって、挿入ソート手法では、最初の要素が常にソートされると想定しているため、2番目の要素から開始します。次に、2番目の要素から最後の要素まで、各要素を前のすべての要素と比較し、その要素を適切な位置に配置します。
擬似コード
挿入ソートの擬似コードを以下に示します。
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure上記は挿入ソートの擬似コードです。次に、この手法を次の例で説明します。
図
ソートされる配列は次のとおりです。
ここで、パスごとに、現在の要素を以前のすべての要素と比較します。したがって、最初のパスでは、2番目の要素から始めます。
したがって、N個の要素を含む配列を完全にソートするには、N個のパスが必要です。
上記の図は、表形式で要約できます。
| パス | ソートされていないリスト | 比較 | ソート済みリスト |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| 二 | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
上の図に示すように、2から始めます。nd最初の要素は常にソートされていると想定しているため、要素。したがって、2番目の要素を最初の要素と比較することから始め、2番目の要素が最初の要素よりも小さい場合は位置を入れ替えます。
この比較と交換のプロセスにより、2つの要素が適切な場所に配置されます。次に、3番目の要素を前の（1番目と2番目の）要素と比較し、同じ手順を実行して3番目の要素を適切な場所に配置します。
このようにして、パスごとに、その場所に1つの要素を配置します。最初のパスでは、2番目の要素をその場所に配置します。したがって、一般に、N個の要素を適切な場所に配置するには、N-1パスが必要です。
次に、C ++言語での挿入ソート手法の実装を示します。
C ++の例
#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < 出力：
二重リンクリストc ++チュートリアル
入力リストは
12 4 3 1 15 45 33 21 10 2
ソートされたリストは
1 2 3 4 10 12 15 21 33 45
次に、挿入ソート手法のJava実装を見ていきます。
Javaの例
public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } } 出力：
要素の入力リスト…
12 4 3 1 15 45 33 21 10 2
要素のソートされたリスト…
1 2 3 4 10 12 15 21 33 45
どちらの実装でも、2からソートを開始していることがわかります。nd配列の要素（ループ変数j = 1）を繰り返し、現在の要素を前のすべての要素と比較し、現在の要素が前のすべての要素と一致していない場合は、要素を並べ替えて正しい位置に配置します。
挿入ソートは最適に機能し、配列が部分的にソートされている場合は、より少ないパスで完了することができます。ただし、リストが大きくなると、パフォーマンスが低下します。挿入ソートのもう1つの利点は、安定ソートであるということです。つまり、リスト内の等しい要素の順序を維持します。
挿入ソートアルゴリズムの複雑さの分析
疑似コードと上の図から、挿入ソートは、バブルソートや選択ソートと比較した場合に効率的なアルゴリズムです。 forループと現在の条件を使用する代わりに、配列がソートされるときに追加のステップを実行しないwhileループを使用します。
ただし、ソートされた配列を挿入ソート手法に渡しても、外側のforループが実行されるため、すでにソートされている配列をソートするにはn個のステップが必要です。これにより、挿入ソートの最適な時間計算量がNの線形関数になります。ここで、Nは配列内の要素の数です。
トレントファイルを開く方法windows10
したがって、挿入ソート手法のさまざまな複雑さを以下に示します。
最悪の場合の時間計算量 O（n 2） ベストケースの時間計算量 オン） 平均時間計算量 O（n 2） スペースの複雑さ O（1）
これらの複雑さにもかかわらず、バブルソートや選択ソートなどの他のソート手法と比較した場合、挿入ソートが最も効率的なアルゴリズムであると結論付けることができます。
結論
挿入ソートは、これまでに説明した3つの手法すべての中で最も効率的です。ここでは、最初の要素が並べ替えられ、すべての要素を前のすべての要素と繰り返し比較してから、現在の要素を配列内の正しい位置に配置すると仮定します。
このチュートリアルでは、挿入ソートについて説明しているときに、1の増分を使用して要素を比較し、それらが連続していることに気付きました。この機能により、ソートされたリストを取得するためにより多くのパスが必要になります。
次のチュートリアルでは、選択ソートを改善した「シェルソート」について説明します。
シェルソートでは、「インクリメント」または「ギャップ」と呼ばれる変数を導入します。これを使用して、リストを「ギャップ」する非連続要素を含むサブリストに分割します。シェルソートは、挿入ソートと比較して必要なパスが少なく、高速です。
今後のチュートリアルでは、データリストの並べ替えに「分割統治」戦略を使用する「クイックソート」と「マージソート」の2つの並べ替え手法について学習します。
=> ここで初心者向けC ++トレーニングガイドに注意してください。
推奨読書