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

2023.04.16
Python

みなさん、こんにちは！

今回は「挿入ソート」について紹介します。

前回は「隣と隣を比較・入れ替え」る「バブルソート」を紹介しました。

魅せるIT編集部

2023.04.15

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

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

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

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

挿入ソートの仕組み

挿入ソートは、配列を並べ替えるための単純なソートアルゴリズムです。

アルゴリズムは、各要素を適切な位置に挿入していくことで、配列を小さい順に並べ替えます。

アルゴリズムの手順は以下の通りです。

ソートする配列の最初の要素を選択し、ソート済みの部分配列とします。
次の要素を未ソートの部分配列から選択します。
選択した要素を、ソート済みの部分配列の適切な位置に挿入します。
2-3を未ソートの部分配列がなくなるまで繰り返します。

ステップ3での要素の挿入は、以下のように行います。

取り出した要素と、それよりも左側にある要素を比較する。
取り出した要素が、比較した要素よりも小さい場合、比較した要素を1つ右にずらす。
1と2を、取り出した要素が挿入されるべき適切な位置が見つかるまで繰り返す。
取り出した要素を、適切な位置に挿入する。

これらの手順を繰り返すことで、配列を昇順にソートすることができます。

このアルゴリズムは、要素数が少ない場合には効率的である一方で、要素数が多い場合には処理速度が遅くなるという欠点があります。

また、ソート済みの部分配列が大きくなると、要素を挿入するために必要な操作が増えるため、処理速度が低下する傾向があります。

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

fig, (ax1, ax2) = plt.subplots(nrows=2, ncols=1, figsize=(8, 8))

ax1.set_xlim(0, len(arr))
ax1.set_ylim(0, 100)
ax1.set_title("Insertion Sort")

ax2.set_xlim(0, len(arr))
ax2.set_ylim(0, 100)
ax2.set_title("Selected Key")

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

# 挿入ソートアルゴリズムの各ステップのフレームを作成する。
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    # key よりも大きい要素を後方に移動する。
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j - 1
        # key と比較して移動する要素を赤色に設定する。
        color = ['gray' if x == i else 'b' for x in range(len(arr))]

        # グラフィック要素を生成する。
        rects = ax1.bar(range(len(arr)), arr, align='edge', width=0.8, color=color)
        rects[j+1].set_height(0)
        key_rects = ax2.bar(range(len(arr)), [0]*len(arr), align='edge', width=0.8, color='g')
        key_rects[j+1].set_height(key)

        # このフレームの Artist 一覧を追加する。
        frames.append((rects + tuple(key_rects)))

    # key を挿入する位置に挿入する。
    arr[j+1] = key
    color = [ 'gray' if x == i else 'b' for x in range(len(arr))]

    # グラフィック要素を生成する。
    rects = ax1.bar(range(len(arr)), arr, align='edge', width=0.8, color=color)
    key_rects = ax2.bar(range(len(arr)), [0]*len(arr), align='edge', width=0.8, color='g')
    key_rects[j+1].set_height(key)

    # このフレームの Artist 一覧を追加する。
    frames.append((rects + tuple(key_rects)))

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

HTML(ani.to_jshtml())

今回はシンプルなソートアルゴリズムである「挿入ソート」について紹介しました。

要素数が少ない場合には効果的なソートです。

ではまた！