挿入ソート(Insertion Sort)

ソート基本

挿入ソートとは

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

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

他のソートには最悪計算時間が\(O(nlogn)\)のものもありますが、挿入ソートの計算量は最悪・平均ともに\(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での例 (Colaboratory などで確認してみて下さい)

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]

ソート基本

Posted by cs-learner