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

[前回] アルゴリズムのモヤモヤを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で解消(2): 挿入ソート