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
#整列後の配列
print(item)
実行結果
#整列前の配列
[11, 42, 5, 63, 37, 54, 4]
#整列後の配列
[11, 5, 42, 37, 54, 4, 63]
※注意点
4行目「for i in range(len(item)-1):」
大小比較をする際、自身と一つ後の要素とを比べているため、ループを1つ減らす。
この実行結果をみて分かること、
＞＞＞配列の中の最大値が最後の要素になった。
＞＞＞最後の要素「63」はもう整列しなくてよい。
＞＞＞残りの6つの要素で同じことを行い、繰り返せばよい！！
プログラムの手順②
すでに整列された要素以外で①を行い、繰り返す。
item = [11,42,5,63,37,54,4]
#整列前の配列
print(item)
for i in range(len(item)-1):
for j in range(len(item)-1-i):
if (item[j] > item[j+1]):
a = item[j]
b = item[j+1]
item[j] = b
item[j+1] = a
#整列後の配列
print(item)
実行結果
#整列前の配列
[11, 42, 5, 63, 37, 54, 4]
#整列後の配列
[4, 5, 11, 37, 42, 54, 63]
以上がバブルソートのアルゴリズムプログラムである。
また、「どのように整列が推移しているのか」「何回整列を繰り返しているのか」などについては、以下の「bubble_sort.py」で確かめることができる。
確認用プログラム
item = [11,42,5,63,37,54,4]
count_compare = 0
count_change = 0
#整列前の配列
print(item)
print("")
for i in range(len(item)-1):
for j in range(len(item)-1-i):
count_compare += 1
if (item[j] > item[j+1]):
a = item[j]
b = item[j+1]
item[j] = b
item[j+1] = a
count_change += 1
print(format(count_compare, "02d"), "回目", item)
#整列後の配列
print("")
print(count_compare, "回比較し、",count_change, "回入れ替えました。")
実行結果
[11, 42, 5, 63, 37, 54, 4]
01 回目 [11, 42, 5, 63, 37, 54, 4]
02 回目 [11, 5, 42, 63, 37, 54, 4]
03 回目 [11, 5, 42, 63, 37, 54, 4]
04 回目 [11, 5, 42, 37, 63, 54, 4]
05 回目 [11, 5, 42, 37, 54, 63, 4]
06 回目 [11, 5, 42, 37, 54, 4, 63]
07 回目 [5, 11, 42, 37, 54, 4, 63]
08 回目 [5, 11, 42, 37, 54, 4, 63]
09 回目 [5, 11, 37, 42, 54, 4, 63]
10 回目 [5, 11, 37, 42, 54, 4, 63]
11 回目 [5, 11, 37, 42, 4, 54, 63]
12 回目 [5, 11, 37, 42, 4, 54, 63]
13 回目 [5, 11, 37, 42, 4, 54, 63]
14 回目 [5, 11, 37, 42, 4, 54, 63]
15 回目 [5, 11, 37, 4, 42, 54, 63]
16 回目 [5, 11, 37, 4, 42, 54, 63]
17 回目 [5, 11, 37, 4, 42, 54, 63]
18 回目 [5, 11, 4, 37, 42, 54, 63]
19 回目 [5, 11, 4, 37, 42, 54, 63]
20 回目 [5, 4, 11, 37, 42, 54, 63]
21 回目 [4, 5, 11, 37, 42, 54, 63]
21 回比較し、 11 回入れ替えました。
一度自分で手を動かしてみると、どう動いているのかよく見えます。
ポイント
基本情報、応用情報で頻出な比較回数に関しては、アルゴリズムをみれば一目瞭然であり、等差数列の和の公式で求めることができる。
S ＝ 1/2*n*(n-1)
まとめ
以上です。いかがだったでしょうか？間違いや改善点など多々あると思いますので、ご指摘よろしくお願いいたします。
また、Qiita初心者でもあるので、見やすいスライドのつくり方などあれば教えてください。