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

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

前回、前々回で「バブルソート」「挿入ソート」をシミュレーションしました。

今回は「選択ソート」を実装してみます。

選択ソートの仕組み

選択ソート(Selection Sort)は、ソートされていない部分から最小の要素を選択し、ソート済み部分の末尾に追加していくことで整列を行うアルゴリズムです。

以下が選択ソートのアルゴリズムの手順です。

1:ソートされていない部分の先頭を指定し、その要素を仮の最小値とする。

2:ソートされていない部分の中から、最小値を持つ要素を見つける。

3:仮の最小値と最小値を交換する

4:ソートされた部分の末尾に仮の最小値を追加する

5:ソートされていない部分が残っている場合は、手順 1 に戻る

以上のステップで並び替えを行っていきます。

Pythonでシミュレーションしてみよう

先ほどの挿入ソートをPythonでシミュレーションしてみましょう。

以下がコードになります。

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, 20)

fig, ax = plt.subplots(figsize=(8, 6))

ax.set_xlim(0, len(arr))
ax.set_ylim(0, 100)
ax.set_title("Selection Sort")

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

# 選択ソートアルゴリズムの各ステップのフレームを作成する。
for i in range(len(arr)):
    # 未ソート部分から最小値を探す。
    min_index = i
    for j in range(i+1, len(arr)):
        if arr[j] < arr[min_index]:
            min_index = j

            
    # グラフィック要素を生成する。
    color = ['gray' if x < i else 'b' for x in range(len(arr))]  # ソート済部分をグレー、未ソート部分を青色に設定する。
    color[min_index], color[i] = 'r', 'r'
    rects = ax.bar(range(len(arr)), arr, align='edge', width=0.8, color=color)
    frames.append(rects)
            
    # 未ソート部分の先頭と最小値を交換する。
    arr[i], arr[min_index] = arr[min_index], arr[i]

    # グラフィック要素を生成する。
    rects = ax.bar(range(len(arr)), arr, align='edge', width=0.8, color=color)
    frames.append(rects)

    # 元に戻す
    color[min_index], color[i] = 'b', 'b'
    rects = ax.bar(range(len(arr)), arr, align='edge', width=0.8, color=color)
    frames.append(rects)

    # 確定したバーを灰色にする
    color = ['gray' if x <= i 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())

以上です!

ではまた!

エラー: データの取得に失敗しました。