アルゴリズムのモヤモヤをPythonで解消(4): 選択ソート

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

## はじめに

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

## 今回のアルゴリズム: 選択ソート

### 問題

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

### 解決案

選択ソートを使用し、解決します。

- Wikipediaから[選択ソート(selection sort)](https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88)
    - ソートアルゴリズムの一つ
    - 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える
    - 最悪時間計算量は O(n2) と遅い
        - 一般にはクイックソートなど、より高速な方法が利用される
    - ただし、以下のケースでは選択ソートが使用される
        - 他の高速な手法は、空間計算量が限られるため使えない
        - ソート対象配列が十分小さく、選択ソートが高速に動作することが保証されている
    - 選択ソートは内部ソートであるため、安定ソートではない(※ 理由は後続)
    - 選択ソートの改良として、ヒープソートが挙げられる

- 選択ソートの手順
    - 1\. 1番目の要素から最後尾の要素まで、最も小さい値を探索
    - 2\. 見つかった要素を、1番目の要素と交換(これで、1番目の要素までソート済み)
    - 3\. 以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換
    - 4\. すべての要素がソート済みになったら処理終了
    - ※ 降順で並べ替える場合も同様で、最小値でなく最大値を探索することで実現
    - ※ 各ループ毎に最小値と最大値両方を探索し、両端の要素を同時に確定させる手法もあり
        - double selection sort

- 選択ソートアルゴリズムの動作例
    - ※ ソート完了した部分は取消し線で表す

8 4 3 7 6 5 2 1 (初期データ)
~~1~~ 4 3 7 6 5 2 8 (1回目のループ終了時)
~~1 2~~ 3 7 6 5 4 8 (2回目のループ終了時)
~~1 2 3~~ 7 6 5 4 8 (3回目のループ終了時)
~~1 2 3 4~~ 6 5 7 8 (4回目のループ終了時)
~~1 2 3 4 5~~ 6 7 8 (5回目のループ終了時)
  ※ この時点で、目視ではソート完了したように見えるが、アルゴリズムは終わっておらず、最後まで処理が必要
~~1 2 3 4 5 6~~ 7 8 （6回目のループ終了時)
~~1 2 3 4 5 6 7 8~~ （7回目のループ終了時)

- 選択ソート計算時間
    - 計算
        - ソートする配列要素数を`n`とする
        - 要素の比較
            - 各ループで`n − 1`回、`n − 2`回、...と行われる
            - 処理全体としては$\sum^{n-1}_{k=1}k$=$\frac{n(n-1)}{2}$回行われる
        - 要素の交換
            - 各ループで最大1回行われる
            - 処理全体では最大`n − 1`回行われる
- 結果
    - 最悪計算時間: O($n^{2}$)
    - 最良計算時間: O($n^{2}$)
    - 平均計算時間: O($n^{2}$)

- 安定性
    - 選択ソートは安定ソートではない
    - 複数の同値の要素を持つ配列に対し、同値の要素同士の順序は保存されない
    - 例えば、配列`(2a 2b 1)`に対し、選択ソートを行う(2a、2bは2と同値だが、区別するためa、bを付ける)
2a 2b 1 (初期状態)
~~1~~ 2b 2a (1回目のループ終了時)
~~1 2b~~ 2a (2回目のループ終了時)
~~1 2b 2a~~ (終了状態)
        - ソート前後で`2a`、`2b`の順序が変更されている
        - これで、安定ソートでないことが確かめられる

### コード

```selection_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 selection_sort(arr):
    for i in range(len(arr)-1):
        min = i
        for j in range(i+1,len(arr)):
            if(arr[j]<arr[min]):
                min=j
            yield arr
        if(min!=i):
            swap(arr,i,min)
            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 = "selection sort"
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    nums = len(arr)
    algo = selection_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=200, repeat=False)
    mng = plt.get_current_fig_manager()
    mng.full_screen_toggle()
    plt.show()
```

- matplotlibがインストールされていない場合
```
$ pip install matplotlib
```
- 実行
```
$ python selection_sort.py
```
- 結果
    - ソート過程が可視化されます

![selection_sort.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/0290d714-cf53-b0aa-dfb7-541e52cf00d4.gif)


## おわりに

Pythonで`選択ソート`アルゴリズムを解いてみました。
計算時間と安定性について、理解を深めることができました。
次回も続きます。お楽しみに。

##### [次回] [アルゴリズムのモヤモヤをPythonで解消(5): マージソート](https://qiita.com/mingchun_zhao/items/29850c6fa514a2840e1f)