3-4. 挿入法（sorting by insertion）
本記事では、整列アルゴリズムにおける挿入法について解説します。
挿入法の考え方
一つの要素を適切な位置に挿入するという単純な操作を繰り返すことによって、結果的に全体を整列します。挿入法の基本となる考え方は、「整列済みのデータに新たな値を一つ追加するとき、その値を適切な位置に挿入すれば、挿入後も整列済みになっている」というものです。
挿入法の前提条件となる整列済みではない場合は、整列されていないところから、一つずつ整列済みの範囲を広げていきます。
最初の範囲は、値は一つだけです。一つですから並び方は1通りです。つまり、一つの値だけを範囲とすれば、昇順であろうと降順であろうと、はじめから整列済みとみなすことができます。
→ アルゴリズムでは、常識にとらわれない柔軟な考え方も必要です。
次に、アルゴリズムとして組み立てるためには、「適切な位置に挿入する」という操作について、もう少し検討する必要がありそうです。まず、「適切な位置に挿入する」ためには、「適切な位置」というのを探さなくてはなりません。
今考えているのは、昇順に整列するというのが目的ですから、挿入後もデータが昇順に並んでいなくてはなりません。したがって、「前のデータ ＜ 挿入するデータ ＜ 次のデータ」となるような位置が、適切な位置になります。この位置を見つけるのは、少し複雑なチェックが必要になりそうですが、前提条件の「整列済み」を忘れてはいけません。
挿入位置を見つけるときの前提として、整列済みであるということが使えます。つまり、「前のデータ ＜ 次のデータ」という条件が成り立っているのです。このことを利用すると、「先頭のデータから順番に値を比べていって、挿入するデータよりも大きな値が見つかったらその前」が適切な挿入位置です。先頭から順に比べていきますから、挿入する値よりも大きな値が見つかった時、その直前のデータは挿入する値よりも小さいものであったはずです。このため、この位置に新しい値を挿入すれば、「前のデータ＜挿入するデータ＜次のデータ」という条件が満たされることになります。
適切な位置が見つかったら、その位置に挿入しますが、その挿入するという処理はそんなに単純ではありません。二つのデータだけが関係するのではありません。挿入位置より後ろのデータをすべて一つずつ後ろにずらす必要があります。
範囲内に挿入位置が見つからない場合には、何もしません。
挿入法の考え方をまとめると
挿入法とは「挿入済みのデータに新たな値を一つ追加するとき、その値を適切な位置に挿入すれば、挿入後も整列済みになる」という考え方に基づく方法でした。そこで、最初は先頭の値だけを整列済みとみなして、2番目の値を挿入します。その結果、1番目～2番目の範囲が整列済みになりますから、今度は、この範囲に3番目の値を挿入します。このように、4番目、5番目と整列済みの範囲を広げていって、最後の値を適切な位置に挿入すれば、結果として全体が整列済みになるのでした。
そして、範囲をひとつずつ広げて繰り返される挿入とは、まず、挿入位置を決定し、その位置に値を挿入するという手順で行いました。挿入位置を決定するためには、整列済みの範囲の先頭から、挿入する値との比較を行い、挿入する値よりも大きな値を探します。見つからなければ、その位置が挿入位置となります。
しかし、整列済みの範囲内に条件を満たす値が見つからないこともあります。この場合には、整列済みの範囲内に条件を満たす値が見つからないこともあります。この場合には、整列済みの範囲の最後の値との比較を終えた時点で、探すのを終了しなくてはいけませんでした。
次に、挿入位置が決定できた場合には、値を挿入します。しかし、挿入の前に、挿入位置以降の値を一つずつ後ろにずらす必要があり、このとき二つの注意がありました。一つは、挿入する要素が上書きされて、なくならないように、変数wに退避することです。そして、もう一つは、後ろから順にずらしていかなくてはならないことです。
挿入法の大まかな構造
挿入処理という部分を、挿入位置を決定して挿入するというようにとらえれば、2番目の値から順に、挿入する値をずらしながら、挿入処理を繰り返すと考えることができます。そして、最後（n番目）の値に対する挿入処理が済んだら、整列は完了ですから、次のようになります。
n ← 7 // データ数
i ← 2
while (i ≦ n)
[i 番目の値に対する「挿入処理」を行う]
i ← i + 1 // 次の値を対象とする
endwhile
※i は2から順に1ずつ増えていき、i=n のときの挿入処理が終わったら終了です。この直後にi は1加算されますから、i = n + 1になったら終了となります。これを継続条件として表すと i ≦ n となります。
挿入処理のアルゴリズム
挿入処理とは、i 番目の値を、1 ～ i-1 番目の範囲の適切な位置に挿入することです。まず、挿入位置の決定、そして、その位置への挿入という流れです。しかし、挿入位置の決定では、見つかった場合と、範囲内に挿入する位置がないので何もしない（そのままの位置でよい）場合がありました。
上記挿入処理を擬似言語で表現する
[挿入位置を決定する]
if (挿入位置が見つかった)
[その位置に値を挿入する]
endif
まず、挿入位置を決定するの部分です。この内容は、1～i-1番目の整列済みの範囲を対象として、i番目の値についての挿入位置を探すというものでした。このとき、i-1番目まで探して見つからないときには、終了しなければいけないことに注意しましょう。
値が配列Aに入っているものとして、値の参照位置は、変数j を使いましょう。1～i-1番目までの値を順に調べていくのですから、jの初期値を1として、順に1ずつ加えながら繰り返すことになります。そして挿入位置が見つかった（A[i] ＜ A[j]）になるか、見つからない（i=j）となったら、繰返しを終了します。
継続条件： A[i] ＜ A[j] とi = j
まず、A[i]＜A[j]ではないのですから、A[i]≧A[j] です。そして、i=jではないのですから i ≠ j です。ただし、変数jの値は1を初期値として増加していき、iとなった時に終了するのですから、j＜i とする方が良いでしょう。
次に、この二つの条件を and でつなぎます。
j ← 1
while (A[i] ≧ A[j] and j ＜ i )
j ← j + 1
endwhile
次は、挿入位置が見つかったという判定です。これは、A[i] ＜A[j] という条件になります。
最後は、その位置に値を挿入する処理です。この部分については、挿入する前に、該当位置以降の値を、それぞれ一つ後ろにずらす必要があります。そして、ずらすときには、後ろの値から先にずらさなくてはいけませんでした。
挿入位置とは、A[i] ＜ A[j] が成立した時の j の位置です。そして、その位置からi-1番目までの値をずらします。しかし、実際には、その逆で、i-1番目、i-2番目、・・、j番目の順にずらしていきます。そして、それぞれの一つ後ろの位置にずらします。
ずらすときに配列の位置を決める変数は、新たにもう一つ必要です。i, j と使いましたから、次は変数k を使うことにします。そうすると、変数kの値をi-1, i-2, ・・、jと1ずつ減らしながら、A[k+1] ← A[k] (A[k] の内容を一つ後ろのA[k+1] に入れる)を繰り返していけばよいので、擬似言語で表現すると、次のようになります。
w ← A[i]
k ← i - 1
while (k ≧ j)
A[k+1] ← A[k]
k ← k - 1
endwhile
A[j] ← w
挿入処理のアルゴリズムをまとめる
[挿入位置を決定する]
if (挿入位置が見つかった）
[その位置に値を挿入する]
endif
j ← 1
while (A[i] ≧ A[j] and i ＞ j）
j ← j + 1 // 挿入位置を決定する
endwhile
if (A[i] ＜ A[j] ) // 挿入位置が見つかった
w ← A[i]
k ← i - 1
while (k ≧ j)
A[k+1] ← A[k]
k ← k - 1
endwhile
A[j] ← w
endif
挿入法のアルゴリズムを仕上げる
n ← 7 // データ数
i ← 2
while (i ≦ n)
[i 番目の値に対する「挿入処理」を行う]
i ← i + 1 // 次の値を対象とする
endwhile
n ← 7
i ← 2
while (i ≦ n)
j ← 1
while (A[i] ≧ A[j] and i ＞ j)
j ← j + 1
endwhile
if (A[i] ＜ A[j])
w ← A[i]
k ← i - 1
while (k ≧ j )
A[k+1] ← A[k]
k ← k - 1
endwhile
A[j] ← w
endif
i ← i + 1
endwhile
補足
この挿入法のアルゴリズムは、挿入ソート（Insertion Sort） の一種です。以下のように、詳細に分解して解説します。
アルゴリズムの概要
挿入ソートは、リストの要素を1つずつ正しい位置に挿入していくソート手法です。基本的な動作は次のようになります。
配列の2番目の要素から処理を開始する。（1番目の要素はすでにソート済みとみなす）
現在の要素を、すでに並んでいる部分と比較し、適切な位置に挿入する。
すべての要素が処理されるまで、ステップ2を繰り返す。
アルゴリズムの分解
1. 初期設定
n ← 7 // 配列の要素数
i ← 2 // 2番目の要素から処理開始
n は配列の要素数（例：7個の要素がある）。
i は現在処理する要素のインデックスで、最初は2番目から始める。
2. ループで各要素を処理
while (i ≦ n)
i を 2 から n まで増やしながら、各要素を正しい位置に挿入していく。
3. 適切な挿入位置を探す
j ← 1
while (A[i] ≧ A[j] and i ＞ j)
j ← j + 1
endwhile
j は、現在の A[i] を挿入する適切な位置を探すための変数。
A[i] が A[j] 以上（A[i] ≧ A[j]）の場合は j を右に進める。
i > j の条件があるので、 j が i に達したらループを抜ける。（探索範囲を超えないようにする）
💡 このループの目的
A[i] の挿入先を決定するために、すでにソート済みの部分 (A[1] から A[i-1]) をスキャンする。
4. 挿入位置が見つかった場合
if (A[i] ＜ A[j])
A[i] が A[j] より小さいなら、A[i] は A[j] より前に移動するべき。
5. 挿入のための準備
w ← A[i]
k ← i - 1
w に A[i] の値を一時保存。
k は A[i] の直前の位置を指す（i-1）。
6. 挿入位置の確保
while (k ≧ j)
A[k+1] ← A[k]
k ← k - 1
endwhile
A[j] に A[i] を挿入するため、A[j] 以降の要素を1つ右へずらす。
k は i-1 から j まで逆方向に走査し、要素を1つずつ右にシフトさせる。
💡 このループの目的
A[i] の値を A[j] に挿入するために、A[j] 以降のデータを後ろにずらす。
7. 挿入の実行
A[j] ← w
w（元の A[i]）を A[j] に代入し、正しい位置に挿入。
8. 次の要素へ進む
i ← i + 1
i を次の要素へ進める。
まとめ
挿入ソートの基本概念
配列の2番目から順に、適切な位置に挿入していく。
挿入位置の探索
j を使って、A[i] を入れる適切な位置を見つける。
要素のシフト
A[j] 以降のデータを後ろにずらしてスペースを作る。
挿入
A[j] に A[i] の値を代入。
次の要素へ進む
i を1つ増やして、次の要素に対して同じ処理を繰り返す。
このアルゴリズムの計算量はO(n²) で、データがほぼソート済みの場合には高速になる特徴があります。
補足2
Java と Python での実装
Java の実装
import java.util.Arrays;
public class InsertionSort {
public static void insertionSort(int[] A) {
int n = A.length;
for (int i = 1; i < n; i++) { // i は 2 から n まで (0-index なので 1 から)
int w = A[i]; // 挿入する値を保持
int j = i - 1;
// A[j] > w の間、要素を右にシフト
while (j >= 0 && A[j] > w) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = w; // 正しい位置に挿入
}
}
public static void main(String[] args) {
int[] array = {5, 3, 8, 6, 2, 7, 4};
System.out.println("Before sorting: " + Arrays.toString(array));
insertionSort(array);
System.out.println("After sorting: " + Arrays.toString(array));
}
}
実行結果
Before sorting: [5, 3, 8, 6, 2, 7, 4]
After sorting: [2, 3, 4, 5, 6, 7, 8]
Python の実装
def insertion_sort(A):
n = len(A)
for i in range(1, n): # i は 2 から n まで (0-index なので 1 から)
w = A[i] # 挿入する値を保持
j = i - 1
# A[j] > w の間、要素を右にシフト
while j >= 0 and A[j] > w:
A[j + 1] = A[j]
j -= 1
A[j + 1] = w # 正しい位置に挿入
# 使用例
array = [5, 3, 8, 6, 2, 7, 4]
print("Before sorting:", array)
insertion_sort(array)
print("After sorting: ", array)
実行結果
Before sorting: [5, 3, 8, 6, 2, 7, 4]
After sorting: [2, 3, 4, 5, 6, 7, 8]
Java と Python の実装のポイント
for ループで i=2 から開始 (0-index のため i=1 から)
while ループで適切な挿入位置を探す
A[j] > A[i] の間、j を左に移動しながら要素を右にシフト
適切な位置に挿入
A[j+1] = w により、保持した値を挿入
以上です。