VSCode × Python でアルゴリズムを動かそう! 挿入法アルゴリズムのアニメーションを作成
本記事では、無料開発環境のVScode とPythonで挿入法アルゴリズムを動かすアニメーションを作成する方法を解説します。
VSCodeのインストール方法などは、交換法アルゴリズムの記事を参照してください。
挿入法アルゴリズム
2番目の要素から開始
最初の要素はすでにソート済みとみなす。
現在の要素を適切な位置に挿入
取り出した要素（キー）を、左側のソート済み部分と比較。
大きい要素を右にずらし、キーを正しい位置に挿入。
次の要素に移動し、同じ操作を繰り返す
ソート済みの範囲を1つずつ広げながら、各要素を適切な位置に挿入。
最後の要素まで繰り返す
配列の全ての要素が適切な位置に挿入されたらソート完了。
特徴
安定性: 安定ソート（同じ値の順番を維持）。
計算量: 平均・最悪ともに O(n2)O(n^2)、ただしほぼ整列済みなら O(n)O(n) で高速。
メモリ: 追加のメモリをほとんど使わない（in-placeソート）。
用途: 小規模なデータや、ほぼ整列されたデータのソートに適している。
挿入法アルゴリズムのアニメーションを作成するPythonコード
import numpy as np
import matplotlib.pyplot as plt
import imageio
import os
def insertion_sort_animation(arr, save_path="insertion_sort.gif"):
frames = []
fig, ax = plt.subplots()
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# プロットの更新
ax.clear()
ax.bar(range(len(arr)), arr, color=["red" if x == i or x == j + 1 else "blue" for x in range(n)])
ax.set_title("Insertion Sort Animation")
ax.set_xlabel("Index")
ax.set_ylabel("Value")
plt.pause(1.0) # 動きを遅くするために時間を増やす
# 一時ファイルとして保存
frame_path = f"frame_{i}.png"
plt.savefig(frame_path)
frames.append(imageio.imread(frame_path))
os.remove(frame_path) # 一時ファイル削除
# GIF保存
imageio.mimsave(save_path, frames, duration=4.0) # GIFの各フレームの表示時間を長くする
print(f"GIF saved as {save_path}")
if __name__ == "__main__":
data = np.random.randint(1, 100, 10) # 10個のランダムな数値
insertion_sort_animation(data)
動画で配列データの移動が確認できます
挿入法アルゴリズムのアニメーション動画（.GIF）
以上です。