はじめに
こんにちは。デジタルステーション習志野スタッフの荒井です。
今回の記事では、大量の数字の列などを並び替えるときに使う「ソートアルゴリズム」について、今回は、基本的な手法の一つである「バブルソート」を紹介したいと思います。
ソートアルゴリズムとは
まず、ソートアルゴリズムとは何か、簡単に説明します。
前提として、アルゴリズムとは、問題を解決するための手順や方法のことを言います。
そして、ソートアルゴリズムとは、大量のデータを、小さい順（昇順）や、大きい順（降順）など特定の並びに整列させるために考え出されたアルゴリズムのことを言います。
PCの処理では、エクスプローラーでのフォルダ管理や、表計算ソフトでの並び替えなど、何かしらのデータを並び替えることが多いです。
そのため、より早く、より少ない試行回数で目的を達成するため、今までに様々な手法が開発されています。
バブルソートとは
バブルソートは、ソートアルゴリズムの一種で、
隣接する配列を比較して、昇順または降順に並べ替える方法です。
この方法は、配列の中での最大値または最小値が、まるで泡のように配列の末尾に浮かんでくることから、バブルソートという名前が付きました。
特徴としては、
- 構造が比較的理解しやすい
- 安定して動作する
- 追加のメモリ容量が必要ない（元の配列を変更するため）
- 計算量が多く、処理は遅くなりがち
などがあげられます。
実際にやってみる
では、実際にPythonを使って、視覚的にバブルソートをやってみましょう。
グラフを扱うので、matplotlibというライブラリを使うと、きれいに作りやすいです。
以下に、サンプルコードを載せておくので、時間がある方はpythonとライブラリをインストールして、.pyファイルで実行してみてください。
import matplotlib.pyplot as plt
import numpy as np
# バブルソート関数（リアルタイムでグラフ更新）
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
# バブルソートのステップ
plt.cla() # 前のグラフを消去
plt.title(f'Bubble Sort - Step {i + 1}, Inner Step {j + 1}')
rect = plt.bar(range(len(arr)), arr, color='blue') # 現在の状態をバーで表示
rect[j].set_color('red') # 入れ替えをわかりやすくするための色付け
rect[j+1].set_color('yellow') # 入れ替えをわかりやすくするための色付け
plt.pause(0.1) # 0.1秒待つ
# グラフを入れ替える場合
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 各ステップごとにグラフを更新
plt.cla() # 前のグラフを消去
plt.title(f'Bubble Sort - Step {i + 1}, Inner Step {j + 1}')
rect = plt.bar(range(len(arr)), arr, color='blue') # 現在の状態をバーで表示
rect[j+1].set_color('red') # 入れ替えをわかりやすくするための色付け
rect[j].set_color('yellow') # 入れ替えをわかりやすくするための色付け
plt.pause(0.1) # 0.1秒待つ
else:
pass
# 初期のデータ（ランダムな整数のリスト）
data = np.random.randint(1, 100, 20)
# グラフを初期化
plt.figure(figsize=(10, 6))
plt.bar(range(len(data)), data, color='blue') # 初期状態を表示
plt.title('Bubble Sort - Initial State')
plt.show()
plt.ion()
# バブルソートを実行
bubble_sort(data)
# ソート終了後に最終的な結果を表示
plt.ioff()
plt.cla()
plt.bar(range(len(data)), data, color='green')
plt.title('Bubble Sort - Sorted')
plt.show()
出力結果は、下の動画のようになります。
まとめ
今回はこれで以上となります。
バブルソートは、基本的な入れ替え手法の一つなので、覚えておくと役に立つ機会もあると思います。
また、グラフの形にして、並び替えている様子を見てみると、アルゴリズムの構造も分かりやすくなりますし、数字が並び替えられているのを見るより面白いと思うので、ぜひ色々なソートアルゴリズムを調べて、遊んでみてほしいと思います。
デジタルステーション習志野
〒274-0063 船橋市習志野台4-1-7 習志野駅前郵便局2F
047-769-7545
