Pythonで単純選択法
はじめに
ここでは、基本・応用情報処理技術者試験を受ける際に学ぶ基本的な整列アルゴリズムについて、実際に自分で手を動かしながら理解した過程を自身への整理も兼ねてまとめています。
私同様にpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、書き方、アルゴリズム等至らない点があると思いますので、細かいことでもご指摘頂ければ幸いです。
宜しくお願い致します。
問題
リスト [11, 42, 5, 63, 37, 54, 4]
について、３つの基本整列法を用いて昇順で整列させなさい（自作問題）
・バブルソート
・単純選択法
・単純挿入法
本スライドでは、単純選択法を扱う。
単純選択法
未配列の要素すべての中から最小値（または最大値）を選択し、未配列部分の先頭要素と入れ替える。この操作を最後から2番目の場所に正しい要素が入るまで、繰り返す。
プログラムの手順①
先頭の要素を最小値と仮定し、その他の要素と順番に比べる。そして、仮定した最小値より小さい要素があれば、その要素を最小値と仮定する。すべての要素と比べ終わり、最小値が決定したら、その値を配列の先頭に挿入する。
item = [11,42,5,26,37,59,4]
#整列前の配列
print(item)
min_item = item[0]
for i in range(len(item)):
if min_item > item[i]:
min_num = i
min_item = item[i]
l = item.pop(min_num)
item.insert(0,l)
#整列後の配列
print(item)
実行結果
#整列前の配列
[11, 42, 5, 26, 37, 59, 4]
#整列後の配列
[4, 11, 42, 5, 26, 37, 59]
※注意点
min_numってなに？
ー＞最小値と決定された要素の添え字
この実行結果をみて分かること
＞＞＞配列の最小値を保存し、その値を要素の先頭に挿入した。（手順に書いてあることと同じ。）
＞＞＞残りの6つの要素で同じことを行い、繰り返せばよい！！
プログラムの手順②
既に整列された要素以外で①を行い、繰り返す。
仮定する最小値の場所を動的にするアルゴリズムを書く。
item = [11,42,5,26,37,59,4]
#整列前の配列
print(item)
for i in range(len(item)-1):
#i番目を最小値と仮定する。
min_item = item[i]
min_num = i
#i番目から最後まで比べる。
for j in range(i+1,len(item)):
if min_item > item[j]:
min_num = j
min_item = item[j]
l = item.pop(min_num)
item.insert(i,l)
#整列後の配列
print(item)
実行結果
#整列前の配列
[11, 42, 5, 26, 37, 59, 4]
#整列後の配列
[4, 5, 11, 26, 37, 42, 59]
※注意点
添え字がややこしいので、実際手を動かしてみましょう。
以上が単純選択法のアルゴリズムプログラムである。
また、「どのように整列が推移しているのか」「何回整列を繰り返しているのか」などについては、以下の「selection_sort.py」で確かめることができる。
確認用プログラム
item = [11,42,5,26,37,59,4]
count_compare = 0
#整列前の配列
print(item)
print("")
for i in range(len(item)-1):
#i番目を最小値と仮定する。
min_item = item[i]
min_num = i
#i番目から最後まで比べる。
for j in range(i+1,len(item)):
if min_item > item[j]:
min_num = j
min_item = item[j]
count_compare += 1
print("最小値を", min_item, "と仮定")
print(format(count_compare,"02d"), "回目", item)
if j==6:
print(" ")
l = item.pop(min_num)
item.insert(i,l)
#整列後の配列
print("")
print(count_compare, "回比較しました。")
実行結果
[11, 42, 5, 26, 37, 59, 4]
最小値を 11 と仮定
01 回目 [11, 42, 5, 26, 37, 59, 4]
最小値を 5 と仮定
02 回目 [11, 42, 5, 26, 37, 59, 4]
最小値を 5 と仮定
03 回目 [11, 42, 5, 26, 37, 59, 4]
最小値を 5 と仮定
04 回目 [11, 42, 5, 26, 37, 59, 4]
最小値を 5 と仮定
05 回目 [11, 42, 5, 26, 37, 59, 4]
最小値を 4 と仮定
06 回目 [11, 42, 5, 26, 37, 59, 4]
最小値を 11 と仮定
07 回目 [4, 11, 42, 5, 26, 37, 59]
最小値を 5 と仮定
08 回目 [4, 11, 42, 5, 26, 37, 59]
最小値を 5 と仮定
09 回目 [4, 11, 42, 5, 26, 37, 59]
最小値を 5 と仮定
10 回目 [4, 11, 42, 5, 26, 37, 59]
最小値を 5 と仮定
11 回目 [4, 11, 42, 5, 26, 37, 59]
最小値を 11 と仮定
12 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 11 と仮定
13 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 11 と仮定
14 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 11 と仮定
15 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 26 と仮定
16 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 26 と仮定
17 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 26 と仮定
18 回目 [4, 5, 11, 42, 26, 37, 59]
最小値を 37 と仮定
19 回目 [4, 5, 11, 26, 42, 37, 59]
最小値を 37 と仮定
20 回目 [4, 5, 11, 26, 42, 37, 59]
最小値を 42 と仮定
21 回目 [4, 5, 11, 26, 37, 42, 59]
21 回比較しました。
ポイント
基本情報、応用情報で頻出な比較回数に関しては、最小値を見つけるための要素数が1つずつ小さくなっているので、等差数列の和の公式で求めることができる。
S ＝ 1/2*n*(n-1)
まとめ
以上です。いかがだったでしょうか？間違いや改善点など多々あると思いますので、ご指摘よろしくお願いいたします。
また、Qiita初心者でもあるので、見やすいスライドのつくり方などあれば教えてください。