[ソート] 挿入ソート

挿入ソート

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

選択ソートと同じように、配列を「ソート済み」と「未ソート」に分けて考えます。

配列の「未ソート」部分の先頭にある要素について、「ソート済み」部分と後方から比較を行っていき、順序関係が合わない場合はソート済み部分を右にシフトします。もし順序関係に合致すれば、空いている箇所に要素を挿入します。

下記は、wikipedia の英語versionにある gif 動画です。

まずは0番目と1番目の要素を比較し、順番が逆であれば入れ換えます。

次に、2番目の要素を、0番目の要素・1番目の要素と比較し、1番目までの要素より小さい場合、正しい順に並ぶように「挿入」します。配列は、前の要素を後ろに一つずつずらします。これで2番目までのソートが完了します。

このあと、3番目以降の要素について、「ソート済みデータと比較し適切な位置への挿入する」という操作を繰り返します。

計算量はバブルソートと同じ\( O (N^2) \)ですが、バブルソートより高速に動作します。

安定ソートで、内部ソートです。

Adaptive algorithm であり、配列がソート済みに近い状態であれば実行速度が上がります。

挿入ソートを一般化するとシェルソートになります。

選択ソートと比較

挿入ソートはオンラインアルゴリズム、選択ソートはオフラインアルゴリズムになります。例えばネット上で配列をダウンロードしてソートするような場合、挿入ソートは配列全体をダウンロードせずともソートを開始することができます。

書き込み回数という観点で考えると、選択ソートは \( O (N) \)ですが、 挿入ソートでは、要素を右シフトすることが多くが\( O (N^2) \)になり、選択ソートが有利になります。

Python で実装

Python で実装します。

import random

def insertion_sort(array):
  for i in range(1, len(array)):
    tmp = array[i]
    k = i
    while k > 0 and array[k - 1] > tmp:
        array[k] = array[k - 1]
        k -= 1
    array[k] = tmp    


if __name__ == '__main__':

  random.seed(1)
  array = [random.randrange(100) for i in range(10)]
  print('未ソート', array)
  # 未ソート [17, 72, 97, 8, 32, 15, 63, 97, 57, 60]

  insertion_sort(array)
  print('挿入ソート', array) 
  # 挿入ソート [8, 15, 17, 32, 57, 60, 63, 72, 97, 97]