【基本情報技術者試験】挿入ソートをPythonで実装

前回に引き続きソートアルゴリズムをPythonで実装していきます。今回は選択ソートを扱います。

1. 基本交換法（バブルソート）
2. 基本選択法（選択ソート）
3. 基本挿入法（挿入ソート）←今回の対象
4. シェルソート
5. クイックソート
6. マージソート
7. ヒープソート

挿入ソートとは？

挿入ソートとは整列してある配列に追加要素を適切な場所に挿入することでソートしていくアルゴリズムのことです。基本挿入法とも呼ばれます。

まず1番目の要素だけソート済みであると考え、2番目の要素が1番目の要素より小さい場合は前に、そうでない場合には後ろに要素を挿入します。すると2番目の要素までソート済みの状態になるので、次に3番目の要素とソート済みの要素を比較しながら3番目の要素を挿入する位置を決めます。これを繰り返していくことによってソートを行います。

例えば4, 2, 5, 3, 1という数列があったときに下記のように更新していきます。（赤字部分が固定箇所になります。）

① 2, 4, 5, 3, 1 （2番目の要素である2は４よりも小さいので、4の前に挿入する）
② 2, 4, 5, 3, 1 （3番目の要素である5は４よりも大きいので、４の後に挿入する（順番はそのまま））
③ 2, 3, 4, 5, 1 （4番目の要素である3は2 < 3 < ４なので、2と4の間に挿入する）
④ 1, 2, 3, 4, 5 （5番目の要素である1は2よりも小さいので、2の前に挿入する）

実際のPythonのコードは下記になります。

listNum = [4, 2, 5, 3, 1]

listNum

[4, 2, 5, 3, 1]

lenNum = len(listNum)
for i in range(1, lenNum):
  j = i
  tmp = listNum[i]
  # すでにソート済みの配列に対して、後ろから順に挿入する場所を求める
  # 挿入することで要素が一つ後ろにずれるので、挿入位置までは一つずつ要素を後ろにずらす
  while listNum[j - 1] > tmp and j > 0: 
    listNum[j] = listNum[j - 1]
    j -= 1
  listNum[j] = tmp

listNum

[1, 2, 3, 4, 5]

挿入ソートでのソート方法は以上となります。
次回はシェルソートをPythonで実装します。