【挿入ソート法とは】リストの昇順・降順ソートの原理と計算量

（単純・基本）挿入ソート法とは？リストを昇順・降順ソートする原理・アルゴリズムについて解説します。

[latexpage]

【挿入ソート法とは】リストを昇順・降順ソート
【計算例】昇順ソート
【計算コスト】挿入ソートの計算時間
【プログラミング】挿入ソートの実装

【挿入ソート法とは】リストを昇順・降順ソート

（単純・基本）挿入ソート法とは、あらかじめソートが終わっているリストに、データを挿入していく整列アルゴリズムです。

順序	操作
①	最悪計算時間がO(n^2)と計算時間が大きい（低速）。
②	整列済みのリストに新しい要素を追加するときは、効率が良い（完全にランダムな並び順だと効率が悪いので適していない）。

【計算例】昇順ソート

理解を深めるために、あらかじめ先頭３つの要素がソート済みである５つの要素をもつリスト[4, 5, 7, 6, 2]の昇順ソートを挿入ソート法で行ってみます。

リストの状態	操作
[4, 5, 7, 6, 2]	4番目の要素（6）とソート済み要素群のうち、一番後ろにある3番目の要素（7）を比較します。4番目の要素（6）の方が小さいので、次に2番目の要素（5）と比較します。
[4, 5,6, 7, 2]	4番目の要素（6）の方が大きので、2番目の要素の後ろに4番目の要素（6）を挿入します(これで1～4番目の要素はソート済となる)。
[2, 4, 5, 6, 7 ]	5番目の要素（2）と4番目の要素を比較します。5番目の要素（2）の方が小さいので、次に3番目、2番目、1番目と順に比較します。1番目まできても5番目の要素（2）の方が小さいので、2は先頭にもっていきます。

【計算コスト】挿入ソートの計算時間

挿入ソート法の処理は、N個の要素を持つリストに対してi = 2, 3, …, Nと同様な操作を繰り返すので、最効率な探索回数は「n + (n-1) + … + 3 + 2 = n(n+1)/2 – 1」となります。
また、要素の比較と入れ替え回数は「(n-1) + (n-2) + … + 3 + 2 = n(n-1)/2」となります。
よって、挿入ソートの計算量は O(n^2) となります。