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

##### [前回] [アルゴリズムのモヤモヤをPythonで解消(1): バブルソート](https://qiita.com/mingchun_zhao/items/679e96f0d3bb90b720c1)

## はじめに

`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)、または基本挿入法](https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88)
    - 整列済み配列部分に追加要素を適切な場所に挿入しながら、ソートを行うアルゴリズム
    - 特徴
        - アルゴリズムが単純で実装が容易
        - 小さな配列に対しては高速
        - 安定ソート(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
```
- 結果
    - ソート過程が可視化されます

![insertion_sort.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/088241bc-02a6-6f0a-6dd9-c8b24897bbb3.gif)


## おわりに

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

##### [次回] [アルゴリズムのモヤモヤをPythonで解消(3): クイックソート](https://qiita.com/mingchun_zhao/items/33fd834b1498ec4f8292)