基本的なSortをmatplotlibでアニメーションにしてみた

03 Feb. 2023追記

前回うまくできなかった barをY軸のValueに合わせてColor gradation　ができるようになったため、こちらの記事に書きました。

tl;dr

• 初めてのApplicationとしてSort appを作成しています。せっかくなので、アニメーションにしてみました
• matplotlibを初めて使いましたが、公式Refが難しく、調べてもなかなかわからないことが多かったです。
• 見た目の良いアウトプットができると人に見せやすくなるので、今後もできるだけアウトプットはしていきたいと思います。

What learned

• yield は関数の途中で一時停止を行うことができる。その際にgenerator objectが帰ってくる。停止場所から再開をすることができる。
• numpy を初めて使ったが割と便利そう。今回はnp.linespace(0, 1, len(n)としてグラフの標準化に使用した。
• アニメーション描画ということで初めて本格的に、Freeのパッケージを触ったが、説明がややこしく一見でほぼ理解できなかった。周辺知識不足とともに、世界中のわかりやすいRefに感謝。
• animation.FuncAnimation にてanimation作成
  • fig: Figure, figure object used to get events
  • func: function to call at each frames. First arg is the next value , and any other args can be supplied
  • frames: Source of each frame of the annimation
• fig, ax = plt.subplots() : return a tuple pf fig and ax

What I couldn't do

• 色々とHelpなど読んでみたが、mp4のsaveができなかった。なぜかシステムエラーにより保存できない？
  • UserWarning: Animation was deleted without rendering anything. This is most likely not intended. To prevent deletion, assign the Animation to a variable, e.g. `anim`, that exists until you output the Animation using `plt.show()` or `anim.save()`.
• barをY軸のValueに合わせてColor gradationすることができなかった。こちらは色々と例があったが、難しくて断念 ><
  • 後日いろいろ調べてできるようになりました！別記事として追記しています。

animation and code

データは全て 0 - 100 のIntをランダム生成して実施
コードは最下部

速度比較表

Sort type	Time(data size: 100)	Time(data size: 1000)	Time(data size: 10000)	Time(data size: 100000)
Insert	0.00011592	0.01380604	1.23332562	127.16356767
Merge	0.00036258	0.00129479	0.01393446	0.17212633
Quick	6.146e-05	0.00086617	0.00872692	0.10575721
Bubble	0.00011304	0.01226279	1.24209742	128.87528279

Insert Sort

Bubble Sort

Merge Sort

Quick Sort

matplotlibのコードはこちら

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import matplotlib as mp
import random
from sort_function_for_visualization import insert_sort, bubble_sort, quick_sort, merge_sort
n = 100

for i in range(n):
    data = [random.randint(0,n) for i in range(n)]

generator = merge_sort(data, 0, n - 1)
sort_name = "merge_sort"

cmap = plt.cm.rainbow(np.linspace(0, 1, len(data)))

fig, ax = plt.subplots()

bar_containers = ax.bar(range(len(data)), data, align="edge", color = cmap)

font = {'family':'serif','color':'blue','size':20}
plt.title(sort_name, fontdict = font)
text = ax.text(0.01, 0.95, "", transform = ax.transAxes)

operation = [0]

def animate(A, bar_containers, operation):
    for bar_container, value in zip(bar_containers, A):
        bar_container.set_height(value)

    operation[0] += 1
    text.set_text("operations : {}".format(operation[0]))

anim = FuncAnimation(fig, func=animate, fargs=(bar_containers, operation), frames=generator, interval=30, repeat=False)

anim.save('./tests/{}.gif'.format(sort_name))
plt.show()

最後に

• 簡単だろうと思っていたが、普通に難しかった。調べてコピペはしたくないが、調べないとできないことが多すぎる。Rome Wasn't Built in a Day もっと精進しなければ