挿入ソート(Insertion Sort)

2019年11月23日ソート基本

挿入ソートとは

挿入ソートとは、安定な内部ソートのアルゴリズムの一つです。小さい要素を前に「挿入」するために、他の要素を前に1つずつ前にずらしていきます。

既にソートされた配列の後ろに、いくつか要素を追加してソートしたい時に高速にソートできます。

他のソートには最悪計算時間が \(O(n \log n)\) のものもありますが、挿入ソートの計算量は最悪・平均ともに \(O(n^2)\) となっています。これは選択ソートやバブルソートなどと同様の計算時間です。

アルゴリズム

ソートしたい配列の要素数をnとすると、以下のアルゴリズムになります。

  1. \(i=1\) から \(n-1\) まで以下をループさせる
    1. \(i\) 番目の値をtmpとして保存する
    2. \(j=i-1\) とする
    3. \(j \ge 0\) かつ \(tmp > arr[j]\) の間、以下をループさせる
      1. \(j\) 番目の値を \(j+1\) 番目に格納する
      2. \(j\) を1減らす
    4. tmpを \(j+1\) 番目に入れる

計算量

時間計算量 (time complexity)

二重のループで表現することができるので、最悪計算量・平均計算量ともに \(O(n^2)\) になります。

最善の計算量は、既に配列がソートされているときで、\(O(n)\) になります。

領域計算量 (space complexity)

配列内で要素をずらしながらソートするので内部ソートとなり、領域計算量は \(O(1)\) です。

問題例: 配列のソート

実際に挿入ソートを用いて配列をソートしてみましょう。今回は \(\{15,38,2,21\}\) という配列を用います。

外側のループ1回目

  1. \(\{15,38,2,21\}\) について 15 は 38 より小さいので、38 をもとの場所に戻して終了

外側のループ2回目

  1. \(\{15,38,2,21\}\) について 38 は 2 より大きいので1つずらす
  2. \(\{15,\_,38,21\}\) について 15 は 2 より大きいので1つずらす
  3. \(\{\_,15,38,21\}\) の先頭に 2 を挿入して終了

外側のループ3回目

  1. \(\{2,15,38,21\}\) について 38 は 21 より大きいので 1 つずらす
  2. \(\{2,15,\_, 38\}\) について 15 は 21 より小さいので、21 を挿入して終了

Pythonでのプログラム例

def insertion_sort(arr):
  n = len(arr)
  for i in range(1, n):
    tmp = arr[i]
    j = i-1
    while j >= 0 and arr[j]>tmp:
      arr[j+1] = arr[j]
      j = j-1
    arr[j+1] = tmp

arr = [15,38,2,21]
insertion_sort(arr)
print(arr) # 出力は[2, 15, 21, 38]

ソート基本