#Pythonで単純挿入法
##はじめに
ここでは、基本・応用情報処理技術者試験を受ける際に学ぶ基本的な整列アルゴリズムについて、実際に自分で手を動かしながら理解した過程を自身への整理も兼ねてまとめています。
私同様にpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、書き方、アルゴリズム等至らない点があると思いますので、細かいことでもご指摘頂ければ幸いです。
宜しくお願い致します。
##問題
リスト [11, 42, 5, 63, 37, 54, 4]
について、３つの基本整列法を用いて昇順で整列させなさい（自作問題）
・バブルソート
・単純選択法
・単純挿入法
本スライドでは、単純挿入法を扱う。
##単純挿入法
未整列の要素の並びの先頭の要素を取り出し、その要素を整列済みの要素の中に正しく挿入していく。
####プログラムの手順①
先頭の要素が次の要素より大きければ、入れ替える。これを繰り返す。
item = [11,42,5,63,37,54,4]
#整列前の配列
print(item)
for i in range(len(item)-1):
if item[i] > item[i+1]:
a = item[i]
b = item[i+1]
item[i] = b
item[i+1] = a
elif item[i] <= item[i+1]:
break
#整列後の配列
print(item)
実行結果
#整列前の配列
[11, 42, 5, 63, 37, 54, 4]
#整列後の配列
[11, 42, 5, 63, 37, 54, 4]
この実行結果をみて分かること、
＞＞＞整列前と整列後で変わっていない？！
＞＞＞11と42の間で大小関係は正しいから、この結果は間違えていない。もし、11が110だったら、、、
item = [110,42,5,63,37,54,4]
#整列前の配列
print(item)
for i in range(len(item)-1):
if item[i] > item[i+1]:
a = item[i]
b = item[i+1]
item[i] = b
item[i+1] = a
elif item[i] <= item[i+1]:
break
#整列後の配列
print(item)
実行結果
#整列前の配列
[110, 42, 5, 63, 37, 54, 4]
#整列後の配列
[42, 5, 63, 37, 54, 4, 110]
このように、次の要素との大小順が正しい位置になるまで比較を続け、挿入する。
####プログラムの手順②
未整列要素部分の先頭と交換された先頭の次の要素の位置を正しい位置に挿入する。つまり、整列部の中で大小関係を正しく守れる位置を確定するために比較をする。
item = [11,42,5,63,37,54,4]
#整列前の配列
print(item)
for i in range(len(item)-1):
if item[i] > item[i+1]:
a = item[i]
b = item[i+1]
item[i] = b
item[i+1] = a
for j in range(0,i):
if item[i-j] < item[i-(j+1)]:
c = item[i-j]
d = item[i-(j+1)]
item[i-j] = d
item[i-(j+1)] = c
elif item[i-j] >= item[i-(j+1)]:
break
#整列後の配列
print(item)
実行結果
#整列前の配列
[11, 42, 5, 63, 37, 54, 4]
#整列後の配列
[4, 5, 11, 37, 42, 54, 63]
以上が単純挿入法のアルゴリズムプログラムである。
また、「どのように整列が推移しているのか」「何回整列を繰り返しているのか」などについては、以下の「insertion_sort.py」で確かめることができる。
###確認用プログラム
item = [11,42,5,63,37,54,4]
count_compare1 = 0
count_compare2 = 0
#整列前の配列
print(item)
print("")
print(format(count_compare1, "02d"), "回目", item)
for i in range(len(item)-1):
count_compare1 += 1
#print(item)
if item[i] > item[i+1]:
a = item[i]
b = item[i+1]
item[i] = b
item[i+1] = a
print(format(count_compare1, "02d"), "回目", item)
for j in range(0,i):
count_compare2 += 1
if item[i-j] < item[i-(j+1)]:
c = item[i-j]
d = item[i-(j+1)]
item[i-j] = d
item[i-(j+1)] = c
print(format(count_compare1+count_compare2, "02d"), "回目", item)
elif item[i-j] >= item[i-(j+1)]:
print(format(count_compare1+count_compare2, "02d"), "回目", item)
break
count_compare1 += count_compare2
count_compare2 = 0
else:
print(format(count_compare1+count_compare2, "02d"), "回目", item)
#整列後の配列
print("")
print(count_compare1, "回比較しました。")
print(item)
実行結果
#整列前の配列
[11, 42, 5, 63, 37, 54, 4]
00 回目 [11, 42, 5, 63, 37, 54, 4]
01 回目 [11, 42, 5, 63, 37, 54, 4]
02 回目 [11, 5, 42, 63, 37, 54, 4]
03 回目 [5, 11, 42, 63, 37, 54, 4]
04 回目 [5, 11, 42, 63, 37, 54, 4]
05 回目 [5, 11, 42, 37, 63, 54, 4]
06 回目 [5, 11, 37, 42, 63, 54, 4]
07 回目 [5, 11, 37, 42, 63, 54, 4]
08 回目 [5, 11, 37, 42, 54, 63, 4]
09 回目 [5, 11, 37, 42, 54, 63, 4]
10 回目 [5, 11, 37, 42, 54, 4, 63]
11 回目 [5, 11, 37, 42, 4, 54, 63]
12 回目 [5, 11, 37, 4, 42, 54, 63]
13 回目 [5, 11, 4, 37, 42, 54, 63]
14 回目 [5, 4, 11, 37, 42, 54, 63]
15 回目 [4, 5, 11, 37, 42, 54, 63]
15 回比較しました。
#整列後の配列
[4, 5, 11, 37, 42, 54, 63]
ここで重要なポイントは、「0回目から1回目」や「6回目から7回目」のように一見何もしていないように見える箇所である。
ここでは、交換され先頭に来た要素が整列部分の中で正しい位置を見つけたときにおこる挙動である。例えば、6回目から7回目では、37の位置をプログラム側が確認している。
##ポイント
基本情報、応用情報で頻出な比較回数に関して、本アルゴリズムは「バブルソート」「単純選択法」とは違い、公式で求めることは難しい。
なぜなら、未整列配列の整列状況によって変わってくるからである。
万が一、すでに整列している要素nの配列を整列する場合、プログラム内の二つ目のfor文に入ることは無く、比較回数は n-1 で求めることができる。
しかしながら、未整列の配列で最悪のパターンである場合、全ての要素を確認しなければならない場合、比較回数は「バブルソート」「単純選択法」と同様、1/2n(n-1) となる。
ここから間接的に分かることは、計算量はfor文の重複度によって決まるということだ。
様々な配列を上記の「insertion_sort.py」に入れて試してみると、徐々に理解できるはずである。
##まとめ
以上です。いかがだったでしょうか？間違いや改善点など多々あると思いますので、ご指摘よろしくお願いいたします。
また、Qiita初心者でもあるので、見やすいスライドのつくり方などあれば教えてください。