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

2023.04.17
Python

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

魅せるIT編集部

2023.04.15

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

https://miseruit.com/2023/04/15/post-4524

こんにちは！今回は「バブルソート」について取り上げます。最近、NHKのピタゴラスイッチで「背の順ソート」というショートムービーを見かけまして、非常に分かりやすく「バブルソート」が紹介されてました。見たことない方は、是非見てみてくださいね！バブルソートの仕組みバブルソートは、隣り合った2つの要素を比較して、必要に応じて交換することで配列をソートするアルゴリズムです。具体的には、配列の先頭から隣り合った2つの要素を比較し、大小関係が逆ならば交換します。そして、配列の末尾まで同様の比較と交換を行います。...

魅せるIT編集部

2023.04.16

python x ソートアルゴリズム | 挿入ソートで並び替えよう！〜アルゴリズムとデー...

https://miseruit.com/2023/04/16/post-4532

みなさん、こんにちは！今回は「挿入ソート」について紹介します。前回は「隣と隣を比較・入れ替え」る「バブルソート」を紹介しました。挿入ソートの仕組み挿入ソートは、配列を並べ替えるための単純なソートアルゴリズムです。アルゴリズムは、各要素を適切な位置に挿入していくことで、配列を小さい順に並べ替えます。アルゴリズムの手順は以下の通りです。ソートする配列の最初の要素を選択し、ソート済みの部分配列とします。次の要素を未ソートの部分配列から選択します。選択した要素を、ソート済みの部分配列の適切な位置に挿...

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

1. 選択ソートの仕組み
2. Pythonでシミュレーションしてみよう
3. 本日のAmazonおすすめ_Top10

選択ソートの仕組み

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

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

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

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

３：仮の最小値と最小値を交換する

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

５：ソートされていない部分が残っている場合は、手順 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())

以上です！

ではまた！