アルゴリズムの基礎: 挿入ソート

アルゴリズムの基礎

勉強がてらに挿入ソートの復習とpythonでの実装をしてみたことのメモです。

単純挿入法(挿入ソート)

整列済みと未整列のデータがあって、未整列のデータを整列済みのデータ列に一つずつ挿入していく方法です。 ここでは、N個の数字を昇順にソートするアルゴリズムとして、挿入ソートを考えてみます。

なお、フローチャートは以下の本を参考に作成しました。

アルゴリズムを、はじめよう

今回のソートでは、リソースは限定しており、データを交換するためのtmp(1つのデータが入るだけ)と元のデータ配列でやりくりします。 そのため、値の入れ替え時にはバブルソートのように一つずつずれていくような動きをします。

ソート例

例として、以下のような5つの数字がランダムに並んでいる場合を考えます。 (tmpは挿入ソート時にデータの格納先として利用します)。 これを挿入ソートに従って、途中まで並べてみます。

1順目 - ソート対象の2つめの箱の値「2」をtmpに退避する - 1つめの箱の値「3」と2つめの箱の値「2」を比較 - 1つめの箱の値のほうが大きいため、値を入れ替える - 1つめの箱の値 → 2つめの箱の値, tmp(2つめの箱の値) → 1つめの箱の値 - 結果: 2 , 3, 5, 1, 4

2順目 - 2つめの箱の値「3」と3つめの箱の値「5」を比較 - 2つめの箱の値のほうが小さいため、既に昇順にソートされているので入れ替えは不要 - 結果: 2 , 3, 5, 1, 4

3順目 - 3つめの箱の値「5」と4つめの箱の値「1」を比較 - 3つめの箱の値のほうが大きいため、入れ替える - 3つめの箱の値 → 4つめの箱の値, tmp(4つめの箱の値) → 3つめの箱の値 - 結果: 2 , 3, 1, 5, 4

• 続けて、2つめの箱の値「3」と3つめの箱の値「1」を比較
  • 2つめの箱の値のほうが大きいため、入れ替える
    • 2つめの箱の値 → 3つめの箱の値, tmp(3つめの箱の値) → 2つめの箱の値
    • 結果: 2 , 1, 3, 5, 4

• さらに、1つめの箱の値「2」と2つめの箱の値「1」を比較
  • 1つめの箱の値のほうが大きいため、入れ替える
    • 1つめの箱の値 → 2つめの箱の値, tmp(2つめの箱の値) → 1つめの箱の値
    • 結果: 1, 2 , 3, 5, 4

4順目 - 4つめの箱の値「5」と5つめの箱の値「4」を比較 - 4つめの箱の値のほうが大きいため、入れ替える - 4つめの箱の値 → 5つめの箱の値, tmp(5つめの箱の値) → 4つめの箱の値 - 結果: 1, 2, 3, 4, 5

フローチャート

上記の実行例からも分かるように、2つのループを持ちます。 未整列のデータを1つ選ぶためのループと 選んだデータをどこに挿入するか値を比較するためのループです。

Pythonでの実装例

Pythonでの実装してみました。

import random

N = 5

# get random array
arr = list(range(1, N+1))
random.shuffle(arr)
print("inital array: {0}".format(arr))

_insert_value = None # a temporary variable for inserting the value
i = 1
k = None

while (i < N):
  _insert_value = arr[i]
  k = i
  print("_insert_value = {0}".format(_insert_value))
  while ( k > 0 and arr[k-1] > _insert_value):
    arr[k] = arr[k-1]
    k = k - 1
  arr[k] = _insert_value
  i = i + 1
  print("i={0}, sorted:{1} , not sorted: : {2}".format(i, arr[:i], arr[i:]))

print("result: {0}".format(arr))

# 実行結果例
inital array: [3, 2, 5, 1, 4]
_insert_value = 2
i=2, sorted:[2, 3] , not sorted: : [5, 1, 4]
_insert_value = 5
i=3, sorted:[2, 3, 5] , not sorted: : [1, 4]
_insert_value = 1
i=4, sorted:[1, 2, 3, 5] , not sorted: : [4]
_insert_value = 4
i=5, sorted:[1, 2, 3, 4, 5] , not sorted: : []
result: [1, 2, 3, 4, 5]