Loading article…
挿入ソートは、比較によって最終的なソート済み配列（またはリスト）を一度に1つずつ構築する単純なソートアルゴリズムです。クイックソート、ヒープソート、マージソートなどのより高度なアルゴリズムに比べて、大規模なリストでは効率が著しく低下します。しかし、挿入ソートにはいくつかの利点があります。
挿入ソートは、入力データを1つずつ消費しながら繰り返し処理を行い、ソート済みの出力リストを生成します。各繰り返し処理において、挿入ソートは入力データから要素を1つ削除し、ソート済みリスト内の適切な位置を見つけてそこに挿入します。入力要素がなくなるまでこの処理を繰り返します。
ソートは通常、配列を順に処理し、その背後にソート済みリストを拡張していくことで、その場で行われます。配列の各位置で、その位置の値がソート済みリスト内の最大値（前の位置でチェックした値）と比較されます。最大値が大きい場合は、その要素をそのままにして次の要素に進みます。小さい場合は、ソート済みリスト内の適切な位置を見つけ、それより大きい値をすべて上に移動してスペースを作り、その適切な位置に挿入します。
k回の反復処理後の結果配列は、最初のk +1個のエントリがソートされているという特性を持ちます（「+1」は最初のエントリがスキップされるためです）。各反復処理では、入力の残りの最初のエントリが削除され、結果の正しい位置に挿入されるため、結果が拡張されます。
になる
xより大きい各要素は、xと比較される際に右にコピーされます。
配列に対して動作する挿入ソートの最も一般的なバリアントは、次のように説明できます。
完全なアルゴリズムの擬似コードを以下に示します。配列はゼロベースです。[ 1 ]
i ← 1 while i < length(A) j ← i j > 0かつA[j-1] > A[j] の間、 A[j] と A[j-1]を交換する j ← j - 1 end while i ← i + 1 end while
外側のループは、最初の要素を除くすべての要素に対して実行されます。これは、単一要素のプレフィックスがA[0:1]自明にソートされているため、最初のエントリがソートされているという不変条件iが最初から真になっているからです。内側のループは要素をA[i]正しい位置に移動するため、ループ終了後には最初のi+1要素がソートされます。andテスト内の演算子は短絡評価を使用する必要があることに注意してください。そうしないと、テストの結果、配列境界エラーj=0が発生し、評価しようとしたときにエラーが発生する可能性がありますA[j-1] > A[j]（つまり、アクセスがA[-1]失敗します）。
（ここで は一時変数です）swapのようにインプレースで操作を展開した後、一度にその位置に移動し、内側のループ本体で 1 つの代入のみを実行する、少し高速なバージョンを作成できます。 [ 1 ]x ← A[j]; A[j] ← A[j-1]; A[j-1] ← xxA[i]
i ← 1 while i < length(A) x ← A[i] j ← i j > 0かつA[j-1] > xの間 A[j] ← A[j-1] j ← j - 1 end while A[j] ← x [ 4 ] i ← i + 1 end while
新しい内部ループは要素を右に移動させて、 のためのスペースを確保しますx = A[i]。
このアルゴリズムは再帰的に実装することもできます。再帰は外側のループを置き換え、自身を呼び出し、n が0 になるまでスタックにnの小さい値を順次格納します。その後、関数は呼び出しチェーンを遡って戻り、 nが1 から始まる各再帰呼び出しの後にコードを実行します。関数の各インスタンスが前のインスタンスに戻るたびにnは1 ずつ増加します。最初の呼び出しは次のようになります。insertionSortR(A, length(A)-1)
function insertionSortR(array A, int n) if n > 0 insertionSortR(A, n-1) x ← A[n] j ← n-1 j >= 0かつA[j] > xの間 A[j+1] ← A[j] j ← j-1 end while A[j+1] ← x end if end function
これはコードを短くするものではなく、実行時間を短縮するものでもありませんが、追加のメモリ消費量をO(1)からO(N)に増加させます（再帰の最も深いレベルでは、スタックには配列へのN個の参照が含まれており、それぞれにNから1までのA変数の値が付随しています）。n
以下はC言語による実装例です。
// 挿入ソートを使用して配列を昇順にソートします。void insertionSort ( int a [], int n ) { // a[0..i-1] をソート済み部分、a[i..end] を未ソート部分として扱います。for ( int i = 1 ; i < n ; i ++ ) { int key = a [ i ]; // ソート済みプレフィックスに挿入する値。int j = i - 1 ;// 'key' が属する位置が見つかるまで、より大きな要素を右に 1 つずつシフトします。 while ( j >= 0 && a [ j ] > key ) { a [ j + 1 ] = a [ j ]; j -- ; }// シフトによってできた隙間に「key」を配置します。a [ j + 1 ] = key ; } }最適な入力は、既にソート済みの配列です。この場合、挿入ソートの実行時間は線形（つまり、O( n )）になります。各反復処理において、入力の残りの最初の要素は、配列のソート済みサブセクションの右端の要素とのみ比較されます。
最も単純な最悪ケースの入力は、逆順にソートされた配列です。すべての最悪ケースの入力の集合は、各要素がその前の要素の中で最小または2番目に小さい値であるすべての配列で構成されます。このような場合、内側のループの各反復では、次の要素を挿入する前に、配列のソートされた部分全体をスキャンしてシフトします。これにより、挿入ソートの実行時間は2次（つまり、O( n² )）になります。
平均的なケースも二次関数的であるため、[ 5 ]大きな配列のソートには挿入ソートは実用的ではありません。しかし、挿入ソートは非常に小さな配列のソートには最も高速なアルゴリズムの 1 つであり、クイックソートよりも高速です。実際、優れたクイックソートの実装では、サブ問題として発生する場合でも、ある閾値より小さい配列には挿入ソートを使用します。正確な閾値は実験的に決定する必要があり、マシンによって異なりますが、一般的には 10 前後です。
例：次の表は、数列 {3, 7, 4, 9, 5, 2, 6, 1} をソートする手順を示しています。各手順において、検討対象のキーには下線が引かれています。前の手順で移動された（または、これまで検討された中で最大であったためそのまま残された）キーにはアスタリスクが付いています。
3 7 4 9 5 2 6 1 3* 7 4 9 5 2 6 1 3 7* 4 9 5 2 6 1 3 4* 7 9 5 2 6 1 3 4 7 9* 5 2 6 1 3 4 5* 7 9 2 6 1 2* 3 4 5 7 9 6 1 2 3 4 5 6* 7 9 1 1* 2 3 4 5 6 7 9
挿入ソートは選択ソートと非常によく似ています。選択ソートと同様に、k回の走査後、最初のk個の要素がソートされた順序になります。しかし、この 2 つのアルゴリズムの根本的な違いは、挿入ソートは現在のキーから逆方向に走査するのに対し、選択ソートは順方向に走査する点です。このため、選択ソートでは最初の k 個の要素はソートされていない入力の最小のk個の要素になりますが、挿入ソートでは単に入力の最初のk個の要素になります。
挿入ソートが選択ソートよりも優れている主な点は、選択ソートではリストの未ソート部分で絶対最小の要素を見つけるために常に残りのすべての要素をスキャンする必要があるのに対し、挿入ソートでは( k + 1)番目の要素がk番目の要素より大きい場合に一度だけ比較すればよいことです。この条件が頻繁に満たされる場合 (入力配列が既にソートされているか部分的にソートされている場合など)、挿入ソートは選択ソートに比べて明らかに効率的です。平均的には(( k + 1)番目の要素のランクがランダムであると仮定した場合)、挿入ソートでは前のk個の要素の半分を比較してシフトする必要があるため、平均的には選択ソートの約半分の比較回数で済みます。
挿入ソートの最悪のケース（入力配列が逆順にソートされている場合）では、挿入ソートは選択ソートと同じ回数の比較を実行します。ただし、選択ソートに対する挿入ソートの欠点は、各イテレーションで( k + 1)番目の要素を配列のソート済み部分に挿入するには、後続のすべての要素をシフトするために多くの要素スワップが必要になるため、書き込み回数が多くなることです。一方、選択ソートでは、各イテレーションで必要なスワップは 1 回だけです。一般に、挿入ソートは配列に O( n 2 ) 回書き込みますが、選択ソートは O( n ) 回しか書き込みません。このため、 EEPROMやフラッシュメモリのように、メモリへの書き込みが読み出しよりも大幅にコストがかかる場合は、選択ソートの方が好ましい場合があります。
クイックソートやマージソートなどの分割統治アルゴリズムは、より大きな配列では挿入ソートよりも高速ですが、挿入ソートや選択ソートなどの非再帰ソートアルゴリズムは、非常に小さな配列（正確なサイズは環境や実装によって異なりますが、通常は7～50要素）では一般的に高速です。したがって、これらのアルゴリズムの実装において有用な最適化は、配列が小さなサイズに分割されたときに、より単純なアルゴリズムを使用するハイブリッドアプローチです。[ 1 ]
DL Shell はアルゴリズムを大幅に改良しました。改良版はShell ソートと呼ばれています。ソートアルゴリズムは、パスごとに距離が小さくなる要素間の距離を比較します。Shell ソートは実用上、実行時間が大幅に改善されており、2 つの単純なバリアントでは、それぞれ O( n 3/2 ) と O( n 4/3 ) の実行時間が必要です。[ 6 ] [ 7 ]
比較のコストがスワップのコストを上回る場合（たとえば、参照によって格納される文字列キーの場合や、人間による操作（並べて表示されたペアの一方を選択するなど）の場合）、バイナリ挿入ソートを使用するとパフォーマンスが向上する可能性があります。[ 8 ]バイナリ挿入ソートは、バイナリサーチを使用して新しい要素を挿入する正しい位置を決定するため、最悪の場合、 ⌈log 2 n ⌉回の比較を実行します。配列内の各要素が検索され挿入される場合、これはO( n log n )です。[ 8 ]アルゴリズム全体としては、各挿入に必要な一連のスワップのため、平均実行時間は依然として O( n 2 ) です。 [ 8 ]
複数の要素を移動する前に位置を計算することで、スワップの回数を減らすことができます。例えば、2つの要素を適切な位置に移動する前に、それらの移動先の位置を計算すると、ランダムデータの場合、スワップの回数を約25%削減できます。極端な場合、この方法はマージソートと同様の動作をします。
バイナリマージソートと呼ばれるバリアントは、バイナリ挿入ソートを使用して32個の要素のグループをソートし、その後マージソートを使用して最終ソートを行います。これは、小さなデータセットでの挿入ソートの速度と、大きなデータセットでのマージソートの速度を組み合わせたものです。[ 9 ]
挿入ごとに一連のスワップを行う必要がないように、入力はリンクリストに格納できます。リンクリストでは、リスト内の位置がわかっている場合、要素を定数時間でリストに追加したり、リストから削除したりできます。 ただし、リンクリストを検索するには、各要素から次の（または前の）要素へのリンクを順番にたどる必要があります。リンクリストはランダムアクセスを持たないため、ソートされていない要素の挿入位置を見つけるためにバイナリサーチなどの高速な方法を使用することはできません。したがって、検索に必要な実行時間は O( n ) であり、ソートに必要な時間は O( n 2 ) です。より高度なデータ構造（ヒープやバイナリツリーなど）を使用すると、検索と挿入に必要な時間を大幅に短縮できます。これがヒープソートとバイナリツリーソートの本質です。
2006年に、Bender、Martin Farach-Colton、およびMosteiroは、配列全体に少数の未使用スペース（つまり「ギャップ」）を残すライブラリソートまたはギャップ挿入ソートと呼ばれる挿入ソートの新しい変種を発表しました。利点は、挿入時にギャップに到達するまで要素をずらすだけで済むことです。著者らは、このソートアルゴリズムがO( n log n )の時間で高い確率で実行されることを示しています。 [ 10 ]
スキップリストを使用すると、挿入時間はO(log n )に短縮され、スキップリストはリンクリスト構造で実装されるため、スワップは不要になります。最終的な挿入の実行時間はO( n log n )になります。
項目が連結リストに格納されている場合、リストはO(1)の追加スペースでソートできます。このアルゴリズムは、最初は空の（したがって自明にソートされた）リストから始まります。入力項目はリストから1つずつ取り出され、ソートされたリストの適切な場所に挿入されます。入力リストが空になると、ソートされたリストは目的の結果になります。
struct LinkedList { int value ; struct LinkedList * next ; };struct LinkedList * sortList ( struct LinkedList * list ) { // リストに要素が 0 個または 1 個ある場合 if ( list == NULL || list -> next == NULL ) { return list ; } // head は結果として得られるソート済みリストの最初の要素ですstruct LinkedList * head = NULL ; while ( list != NULL ) { struct LinkedList * current = list ; list = list -> next ; if ( head == NULL || current -> value < head -> value ) { // ソート済みリストの先頭に挿入// または、空のソート済みリストの最初の要素として挿入current -> next = head ; head = current ; } else { // 現在の要素を空でないソート済みリストの適切な位置に挿入struct LinkedList * p = head ; while ( p != NULL ) { // ソート済みリストの最後の要素とリストの中央をチェックif ( p -> next == NULL || current -> value < p -> next -> value ) { // ソート済みリストの中央または最後の要素として挿入current -> next = p -> next ; p -> next = current ; break ; // 完了} p = p -> next ; } } } return head ; }以下のアルゴリズムは、ソート済みリストへの挿入に末尾ポインタ[ 11 ]を使用します。より単純な再帰的な方法では、（スプライシングではなく）毎回リストを再構築し、O( n )のスタック領域を使用できます。
struct LinkedList * sortList ( struct LinkedList * list ) { // リスト内の要素がゼロまたは1つの場合 if ( list == NULL || list -> next == NULL ) { return list ; }// 空のリストからソート済み配列を構築するstruct LinkedList * sorted = NULL ;// 入力リストから項目を 1 つずつ取り出して空にするwhile ( list != NULL ) { // 先頭を記憶するstruct LinkedList * head = list ; // 効率的なスプライスのための末尾ポインタstruct LinkedList ** trail = & sorted ;// リストから先頭の項目を削除するlist = list -> next ;// 適切な場所にヘッドをソート済みリストに挿入する// 'head' はここに属しているか? while ( ! ( * trail == NULL || head -> value < ( * trail ) -> value )) { // いいえ - リストを下に進むtrail = & ( * trail ) -> next ; }head -> next = * trail ; * trail = head ; }ソートされた値を返す; }