python x ソートアルゴリズム | バブルソートで並び替えよう！〜アルゴリズムとデータ構造

2023.04.15
Python

こんにちは！

今回は「バブルソート」について取り上げます。

最近、NHKのピタゴラスイッチで「背の順ソート」というショートムービーを見かけまして、非常に分かりやすく「バブルソート」が紹介されてました。

見たことない方は、是非見てみてくださいね！

1. バブルソートの仕組み
2. Pythonでアニメーションを作ろう
3. 本日のAmazonおすすめ_Top10

バブルソートの仕組み

バブルソートは、隣り合った2つの要素を比較して、必要に応じて交換することで配列をソートするアルゴリズムです。

具体的には、配列の先頭から隣り合った2つの要素を比較し、大小関係が逆ならば交換します。そして、配列の末尾まで同様の比較と交換を行います。

このようにして、最大値が配列の末尾に移動することが保証されます。

次に、配列の先頭から末尾を除いた範囲で同様の比較と交換を繰り返し、2番目に大きな値が2番目の末尾に移動することを保証します。

同様の手順を、配列の先頭から、配列全体が昇順になるまで繰り返します。

安定なソートアルゴリズムであり、また、比較と交換のみを行うため、メモリ使用量が少なくて済むという利点があります。

しかし、データセットのサイズが大きい場合は非常に遅いため、実用的ではありません。

Pythonでアニメーションを作ろう

上記のバブルソートをpythonを使ってシミュレーションしてみましょう。

アニメーションとして利用するライブラリとしては、matplotlib.animationを利用します。

プログラムは以下の通りです。

import matplotlib.pyplot as plt
import numpy as np
from IPython.display import HTML
from matplotlib.animation import ArtistAnimation

# バブルソートに使用する整数の配列を生成
arr = np.random.randint(1, 100, 10)

fig, ax = plt.subplots(facecolor="w")
ax.set_xlim(0, len(arr))
ax.set_ylim(0, 100)

frames = []  # 各フレームを構成する Artist 一覧

# バブルソートアルゴリズムの各ステップのフレームを作成する。
for i in range(len(arr)):
    for j in range(len(arr)-i-1):
        # スワップする要素を決定する。
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
        color = ['gray' if x >= len(arr)-i else ('r' if x == j or x == j+1 else 'b') for x in range(len(arr))]
        rects = ax.bar(range(len(arr)), arr, align='edge', width=0.8, color=color)
        frames.append(rects)

# アニメーションを作成する。
ani = ArtistAnimation(fig, frames, interval=200)

HTML(ani.to_jshtml())

以下のようなアニメーションが表示されればOKです。