週間プログラミング⑤：バブルソートを可視化してみよう
記事IT・テクノロジー
今回はバブルソートを可視化してみましょう。
ソートとは
アルゴリズムにおけるソートとは、数字や文字の並べ替えのことを指します。
より一般的には、数値の並べ替えのことをソートということが多いです。
例えば
１ ５ ２ ４
という数列を
１ ２ ４ ５
や
５ ４ ２ １
と並べ直すのがソートです。
バブルソートとは
ソートには様々なアルゴリズムがあるのですが、その中でも特に直感的でわかりやすいのがバブルソートです。
私たちが数字を大きい順に並べ替えるとき、数字が一番大きいものを中から見つけてを、それを左側に寄せていくということを繰り替えすと思います。
つまり、次のような数列があったとき
２ ９ ４ ５
このように、
２ ４ ９ ５
↓
２ ４ ５ ９
と並べ替えるはずです。
このように、大きい数字が右側に登っていく様を「バブル」と表現します。
先にこの記事の成果物を示しましょう。
赤い棒が「泡」のように右側に登っていくのが分かると思います。
バブルソートのコーディング
バブルソートの可視化GIFアニメーションを作っていきます。
モジュール類
まずモジュール類をインポートします
#乱数発生
import random
#作図
import matplotlib.pyplot as plt
＃ディレクトリの操作
import os
#GIFの作成
from PIL import Image
GIFの素材画像と出力先の設定
#シミュレーション結果の出力先
di = "./"
pics = di + "bubble_sort_pics/"
gif = di + "simulation_results/"
#のフォルダ作成
try:
os.mkdir(pics)
os.mkdir(gif)
except:
pass
画像の出力
関数を作ります。
わかりやすいように「バブル」を赤で、整列範囲を黄色で示します。
def make_fig(height,t,c1,c2):
picsfname = pics + str(t) + ".png"
pictitle = "No." + str(t)
colors = ["b" for i in range(20)]
colors[c1] = "r"
colors[c2] = "y"
plt.figure()
plt.title(pictitle)
plt.bar(left,height,color=colors)
plt.savefig(picsfname)
plt.close()
ソート対象の乱数列の生成
xにソート対象を格納します。
leftはグラフを作るときの横軸です。
x = []
left = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
c = 0
#１～２０までの数字を格納する
#全ての数字を一つずつ出現させる処理を付ける
while len(x) < 20:
tmp = random.randint(1,20)
if tmp not in x:
x.append(tmp)
バブルソート
バブルソートの中心部です。
一番大きい値を右側に寄せるために、整列範囲を保持するループ（i）と、左側に大きい数字があれば、右側に寄せる処理のループ（j）を２重に組み合わせます。
もし一回も入れ替えが発生しなければ、ソートは終了になります。
入れ替えの事実をフラグ（f）に保持しておき、0なら終了します。
for i in range(19,0,-1):
f = 0
for j in range(i):
make_fig(x,c,j,i)
c += 1
if x[j] > x[j+1]:
tmp = x[j]
x[j] = x[j+1]
x[j+1] = tmp
f = 1
if f == 0:
break
GIFの作成
make_fig(x,c,i,1)
c += 1
frames = []
giffname = gif + "simulation.gif"
#画像の読み込み
for i in range(c):
picname = pics + str(i) + ".png"
new_frame = Image.open(picname)
frames.append(new_frame)
#gif化
frames[0].save(giffname,
format='GIF',
append_images=frames[1:],
save_all=True,
duration=30,
loop=0)
ソースコード全体
import random
import matplotlib.pyplot as plt
import os
from PIL import Image
#シミュレーション結果の出力先
di = "./"
pics = di + "bubble_sort_pics/"
gif = di + "simulation_results/"
#のフォルダ作成
try:
os.mkdir(pics)
os.mkdir(gif)
except:
pass
def make_fig(height,t,c1,c2):
picsfname = pics + str(t) + ".png"
pictitle = "No." + str(t)
colors = ["b" for i in range(20)]
colors[c1] = "r"
colors[c2] = "y"
plt.figure()
plt.title(pictitle)
plt.bar(left,height,color=colors)
plt.savefig(picsfname)
plt.close()
x = []
left = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
c = 0
while len(x) < 20:
tmp = random.randint(1,20)
if tmp not in x:
x.append(tmp)
for i in range(19,0,-1):
f = 0
for j in range(i):
make_fig(x,c,j,i)
c += 1
if x[j] > x[j+1]:
tmp = x[j]
x[j] = x[j+1]
x[j+1] = tmp
f = 1
if f == 0:
break
make_fig(x,c,i,1)
c += 1
frames = []
giffname = gif + "simulation.gif"
#画像の読み込み
for i in range(c):
picname = pics + str(i) + ".png"
new_frame = Image.open(picname)
frames.append(new_frame)
#gif化
frames[0].save(giffname,
format='GIF',
append_images=frames[1:],
save_all=True,
duration=30,
loop=0)
print("finished")
まとめ
これを実行して、
./bubble_sort_pics に図が、
./simulation_results にgifがあれば成功です。
一応下に示すのがgifファイルですが、この記事内では動かせませんので、ご自身の環境をいじってみてください。
