アルゴリズムのモヤモヤをPythonで解消(2): 挿入ソート

[前回] アルゴリズムのモヤモヤをPythonで解消(1): バブルソート

はじめに

Pythonでアルゴリズムを楽しむ、第2弾です。

理論: アルゴリズムの性能評価指標

計算量による評価

• 時間計算量
  • 単位は、必要な処理/操作回数(ステップ数)
    • 処理時間(秒など)は、実行環境(ハードウェア/ソフトウェア)に依存するため使用しない
• 空間計算量
  • 記憶容量(メモリ)がどれだけ必要か

O記法(オーきほう、OはOrder)

• 計算量の表記法
  • 例えば、データの数nに比例し、計算量増加する場合
    • O(n)と表す

表記	意味	例
O(1)	定数	配列を添字アクセスする場合
O($log\ {n}$)	対数	二分探索
O(n)	1次	線形探索
O($n\ log\ {n}$)	ランダウ	クイックソート
O($n^{2}$)	2次	バブルソート、2次元配列走査(2重ループ)
O($n^3$)	3次	3次元配列走査(3重ループ)
O($2^n$)	指数	集合分割問題

• 表で上の方にあるほど、計算量が小さく効率的
• ただし、データの数nの大きさにより、逆転する可能性あり

最悪/最良/平均計算時間

同じアルゴリズムでも、入力データのサイズや並びによって計算量が変わる。

• 最悪計算時間
  • 最も計算量がかかるデータでの計測結果
  • 多くの場合、最悪時の計算量を使用
• 最良計算時間
  • 最も計算量が少ないデータでの計測結果
• 平均計算時間
  • 最悪なパターンが起こらない場合は、平均的な計算量を使用

前回取り上げたバブルソートの計算量

• 最悪計算時間: O($n^{2}$)
• 最良計算時間: O($n$)
• 平均計算時間: O($n^{2}$)

最良(最短)と最悪(最長)で、かなり差が開いていますね。

今回登場するアルゴリズム: 挿入ソート

問題

以下8つの数字を昇順で整列せよ。
8 4 3 7 6 5 2 1

解決案

挿入ソートを使用し解決します。

• Wikipediaから挿入ソート(insertion sort)、または基本挿入法

  • 整列済み配列部分に追加要素を適切な場所に挿入しながら、ソートを行うアルゴリズム
  • 特徴
    • アルゴリズムが単純で実装が容易
    • 小さな配列に対しては高速
    • 安定ソート(stable sort)
      • ソート途中の各状態において、常に順位の位置関係を保っていること
    • in-placeアルゴリズム
      • データ構造の変換にあたって、追加の記憶領域をほとんど使わずに行うアルゴリズム
      • in-place とはその場でといった意味で、入力が出力で上書きされることに由来する用語
    • オンラインアルゴリズム(Online algorithm)
      • 入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズム
      • 対して、オフラインアルゴリズム(Offline algorithm)は
        • 問題を解くため、最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズム
    • ※ 挿入ソートを高速化したソート法
      • シェルソート(今後取り上げます)

• 計算量

  • 最悪計算時間: O($n^{2}$)
  • 最良計算時間: O($n$)
  • 平均計算時間: O($n^{2}$)

• ソートの手順

  • 1. 0番目の要素を、1番目の要素と比較
    • 順番が逆であれば入れ換える
  • 2. 2番目の要素を、1番目までの整列済み要素と比較
    • 小さい場合、正しい順に並ぶように挿入
      • 配列への挿入は、前の要素を後ろに一つずつずらす
      • この操作で、2番目までのデータが整列済みとなる
      • ただし、さらにデータ挿入される可能性あるので未定
  • 3. 3番目以降の要素を、整列済みデータと比較
    • 適切な位置へ挿入
  • 4. 残りの要素に対しても、上述の比較と挿入を繰り返す

• アルゴリズムの動作例

※ 挿入する部分を太文字で表す
※ 整列された部分に取消し線を引く

8 4 3 7 6 5 2 1 (初期データ)
4 8 3 7 6 5 2 1 (1回目のループ終了時、8と4が入れ替わった)
3 4 8 7 6 5 2 1 (2回目のループ終了時、3が整列済み部分に挿入された(4の前に))
3 4 7 8 6 5 2 1 (3回目のループ終了時)
3 4 6 7 8 5 2 1 (4回目のループ終了時)
3 4 5 6 7 8 2 1 (5回目のループ終了時)
2 3 4 5 6 7 8 1 (6回目のループ終了時)
1 2 3 4 5 6 7 8 (7回目のループ終了時。ソート完了)

コード

insertion_sort.py

import matplotlib.pyplot as plt
import matplotlib.animation as ani
import matplotlib.cm as cm

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def insertion_sort(arr):
    if len(arr) == 1:
        return
    yield arr
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j - 1] > arr[j]:
            yield arr
            swap(arr, j, j-1)
            j -= 1
    yield arr

def plot(arr, rec, epochs):
    for rec, val in zip(rec, arr):
        rec.set_height(val)
        rec.set_color(cm.tab20(val % 15))
    text.set_text("count: {}".format(epochs[0]))
    epochs[0] += 1

if __name__ == '__main__':
    title = "insertion sort"
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    nums = len(arr)
    algo = insertion_sort(arr)
    fig, ax = plt.subplots()
    ax.set_title(title)
    bar = ax.bar(range(len(arr)), arr, align='edge')
    ax.set_xlim(0, nums)
    ax.set_ylim(0, int(nums * 1.1))
    text = ax.text(0.01, 0.9, "", transform=ax.transAxes)
    epochs = [0]
    anim = ani.FuncAnimation(fig, func=plot, fargs=(bar, epochs), frames=algo, interval=1000, repeat=False)
    mng = plt.get_current_fig_manager()
    mng.full_screen_toggle()
    plt.show()

• matplotlibがインストールされていない場合

$ pip install matplotlib

• 実行

$ python insertion_sort.py

• 結果
  • ソート過程が可視化されます

おわりに

Pythonで挿入ソートアルゴリズムを解いてみました。
計算量はバブルソートと変わらず、遅いです。
ただし、上述の特徴から実際使用されているようです。
次回も、Pythonによるアルゴリズム勉強続きます。お楽しみに。

[次回] アルゴリズムのモヤモヤをPythonで解消(3): クイックソート