あわあわアニメーションでバブルソート

整列アルゴリズムのうち最も基本的な「バブルソート」。

その名前の由来は「泡」です。泡が浮き上がってくるように、そーっとソートされます。よって、泡でバブルソートするアニメーションを作ってみましょう。

泡

import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure()

ims = []
for _ in range(30):
    image = []
    for _ in range(30):
        image += plt.plot(random.randint(10, 100), random.randint(10, 100), 
                          markersize=random.randint(10, 100), marker="o", c="white", 
                          markeredgecolor="blue", alpha=0.5)
    ims.append(image)
        
# 動画に変換する
ani = animation.ArtistAnimation(fig, ims, interval=100, repeat_delay=1000)
ani.save("bubble.gif", writer='pillow') # gif ファイルとして保存
HTML(ani.to_jshtml()) # HTML上で表示

ほーら、泡っぽいでしょう？ 何をイメージしました？ 炭酸飲料？ ビール？

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。

泡ソート

import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

def bubble_sort(data, x=0):
    movie = [] # 動画＝静止画の集合を格納するリスト

    image = []
    for i in range(len(data)):
        im1 = plt.plot(x, i, markersize=data[i], marker="o", c="white", 
                       markeredgecolor="blue", alpha=0.5)
        image += im1
    movie.append(image) # 静止画を１つ追加する

    for index in range(len(data)-1, 0, -1):
        for low in range(index):
            image = []
            for i in range(len(data)):
                if i == low or i == low + 1:
                    color = "skyblue"
                else:
                    color = "white"
                
                im1 = plt.plot(x, i, markersize=data[i], marker="o", c=color, 
                               markeredgecolor="blue", alpha=0.5)
                im2 = plt.plot(x, i, markersize=20, marker="$" + str(data[i]) + "$", 
                               c="blue", alpha=0.5)
                image += im2
                image += im1
                
            movie.append(image)

            if data[low] > data[low+1]:
                tmp = data[low+1]
                data[low+1] = data[low]
                data[low] = tmp
                
                image = []
                for i in range(len(data)):
                    if i == low or i == low + 1:
                        color="cyan"
                    else:
                        color="white"
                        
                    im1 = plt.plot(x, i, markersize=data[i], marker="o", c=color, markeredgecolor="blue", alpha=0.5)
                    im2 = plt.plot(x, i, markersize=20, marker="$" + str(data[i]) + "$", c="blue", alpha=0.5)
                    image += im2
                    image += im1
                movie.append(image)
                
    return movie

data = [(i + 1) * 10 for i in range(10)]
random.shuffle(data)

fig = plt.figure(figsize=(8, 8))
movie1 = bubble_sort(data)

ani = animation.ArtistAnimation(fig, movie1, interval=1000, repeat_delay=1000)
ani.save("bubble_sort.gif", writer='pillow') # gif ファイルとして保存
HTML(ani.to_jshtml()) # HTML上で表示

これはどうみてもバブルソートです。ありがとうございます。

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。

最後に

ええ、相当がんばって作りました。ソートだけに。