#Pythonで学ぶアルゴリズム< 挿入ソート >
##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第16弾として挿入ソートを扱う．
##挿入ソート
リストの先頭から順にソート済みとして，その隣のデータを挿入データとする．それから挿入データがソート済みのデータの中のどこに位置するのかというのをソート済みデータの末尾から順に比較し必要があれば入れ替えを行い，所望の位置に移動させる．そのイメージ図を次に示す．
上図のように，ソート済みデータを拡張していくような形で徐々に昇順に並べ替えられていく様子が分かる．
##実装
先ほどの手順に従ったプログラムのコードとそのときの出力を以下に示す．
#####コード
"""
2021/01/09
@Yuya Shimizu
挿入ソート
"""
def insert_sort(data):
"""挿入ソート：少しずつソート済み箇所を広げ，昇順に並べ替える"""
#1つずつ挿入データを吟味する
for i in range(1, len(data)):
temporary = data[i] #挿入データを一時的に記録
j = i - 1
while (j >= 0) and (data[j] > temporary): #挿入データがソート済みデータ内のデータよりも小さく右にあれば繰り返し入れ替え
data[j + 1] = data[j] #右へ1つデータを移す
j -= 1
data[j + 1] = temporary #上の操作で移動を終えた所に一時的に記録していた挿入データを代入
return data
if __name__ == '__main__':
DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sorted_data = insert_sort(DATA.copy())
print(f"{DATA} → {sorted_data}")
#####出力
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
ちゃんと昇順に並べ替えられていることが分かる．
今回は並べ替える前後での比較をしたいがために，あえてsorted_dataという変数に結果を格納し，さらに関数への引数はDATA.copy()というようにcopy関数により，引数に影響が出ないようにしている．並べ替えるだけなら，そのような操作は必要でなく，insert_sort(DATA)とすればよい．
##挿入ソートの計算量
最後に計算量について触れる．
基本的に選択ソートと同様，**計算量はオーダー記法で表すと，$O(n^2)$となる．
ただし，一度も交換が発生しない場合は，比較のみ（入れ替えなし）で済むため$O(n)$**となる．
##感想
前回に引き続き，そこまで複雑ではなかった．後ろから並べ替えることにはなるほどと学べた．次回以降の並べ替えアルゴリズムも楽しみである．
##参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社