# クイックソート
# 入れ替えるメソッド
def swap(a: list,x: int,y: int):
t = a[x]
a[x] = a[y]
a[y] = t
return a
# ソートするメソッド
def quick(a: list,left: int,right: int) -> list:
pl = left # 左カーソル
pr = right # 右カーソル
pivot = a[int((pl+pr)/2)] # 枢軸(中央の要素)
# 配列の分割
while True:
# a[pl] >= pivot となる要素が見つかるまで右に走査
while a[pl] < pivot:
pl += 1
# a[pr] <= pivot となる要素が見つかるまで左に走査
while a[pr] > pivot:
pr -= 1
if pl <= pr:
a = swap(a,pl,pr)
pl += 1
pr -= 1
if pl > pr:
break
# 再帰
if left < pr:
a = quick(a,left,pr)
if pl < right:
a = quick(a,pl,right)
return a
if __name__ == "__main__":
print("quick sort test")
import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
#fig = plt.figure()
fig, ax = plt.subplots(figsize=(4, 4))
ax.grid()
plotdata =[]
test = [random.randrange(1,100,1) for i in range(100)]
#print(test)
plotdata.append(ax.bar([i for i in range(100)],height=test,color="steelblue",edgecolor='none'))
def plot_quick(a: list,left: int,right: int) -> list:
pl = left; pr = right; pivot = a[int((pl+pr)/2)]
while True:
while a[pl] < pivot:
pl += 1
while a[pr] > pivot:
pr -= 1
if pl <= pr:
a = swap(a,pl,pr)
pl += 1
pr -= 1
if pl > pr:
break
plotdata.append(ax.bar([i for i in range(100)],height=a,color="steelblue",edgecolor='none'))
if left < pr:
a = plot_quick(a,left,pr)
if pl < right:
a = plot_quick(a,pl,right)
return a
test = plot_quick(test,0,len(test)-1)
#print(test)
plotdata.append(ax.bar([i for i in range(100)],height=test,color="steelblue",edgecolor='none'))
anim = animation.ArtistAnimation(
fig,
plotdata,
interval = 200
)
anim.save("res_quick_sort.mp4", writer = 'ffmpeg')
anim.save("res_quick_sort.gif", writer='imagemagick')
print("finish")
以上においてmp4,gifアニメ化するには,以上のスクリプトと同じディレクトリ下にffmpegがあるか,ffmpegがインストールされている状態でなければなりません. imagmagickについても同じです. どちらもLinux(私はWSLのUbuntuで試してみましたが)環境ならば,
sudo apt-get install ffmpeg sudo apt-get install imagemagick
でインストールできます.
スクリプトを実行したときにできるgif画像が以下です. 値はランダムに設定しているため,実行すると,毎回変わりますので以下と同じ画像にはなりません. gif画像ならはてなブログに簡単に貼れるので便利.ですが,mp4よりサイズが大きくなってしまいました...
もう一つ注意すべきことがあります.
WSLで以上のスクリプトを実行すると,
qt.qpa.screen: QXcbConnection: Could not connect to display :0.0 Could not connect to any X display.
というエラーが出ます. matplotlib・ffmpeg・imagemagickのいずれかが原因のような気がします. とりあえず,このエラーを解消するには kusoimox.hatenablog.jp でやったのと同じようにXlaunch をスクリプトを実行する前に起動しておくことです. (やり方はこちらのサイトを参考に) そうすると,スクリプトが実行されます. その際に
QStandardPaths: XDG_RUNTIME_DIR not set, defaulting to '/tmp/runtime-ユーザ名'
と出ますが,スクリプトは最後まで実行されますので気にしなくてもよいでしょう.
参考リンク
- [matplotlib animation] 43. データの追加によるヒストグラムの形状変化アニメーション – サボテンパイソン
- Python - python ヒストグラムのアニメーション|teratail
- Matplotlib - MatplotlibのFuncAnimationが動きません。|teratail
- random --- 擬似乱数を生成する — Python 3.8.1 ドキュメント
- matplotlibで簡単にアニメーションをつくる(mp4, gif) - Qiita
- Pythonではじまる、型のある世界 - Qiita
- Pythonで変数宣言をしたい - AI人工知能テクノロジー