挿入ソート
挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
出典: フリー百科事典『ウィキペディア（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]
