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

## はじめに

アルゴリズムと言えば、どうしても堅苦しいイメージが。
`Pythonでアルゴリズムを楽しむ`、が本連載の趣旨です。

`正解を見つける`、がゴールでなく、
`考える力を身につける`、をゴールとしたいです。
- 3つ以上解き方を見つける
- そこからベスト解を選ぶ

## 改めて、アルゴリズムとは

### アルゴリズムの定義

`JIS X 0001:1994`による定義

- 問題を解くためのもので
- 明確に定義され
- 順序付けられた有限個の規則からなる集合

### アルゴリズム良し悪しの評価基準

- 機能性
    - 目的に対する適合性、正確さ
- 使用性
    - 理解しやすさ、目的/意図のわかりやすさ
- 効率性
    - 実行性能、時間効率/資源効率
- 保守性
    - 仕様変更と追加など保守のしやすさ
- 移植性
    - 別環境への移植のしやすさ

### アルゴリズムの分類

- ソート
- 文字列
- 探索
- マージ
- 数値
- グラフ
- 計算幾何
- 組合せ
- 機械学習
- 暗号化
- データ圧縮
- 構文解析

## 改めて、Pythonとは

Wikipediaから[Pythonとは](https://ja.wikipedia.org/wiki/Python)

- インタープリタ型の高水準汎用プログラミング言語
- 明確で論理的なコーディング支援が目的で、コードの可読性を重視
- 動的型付けで、値やオブジェクトの型安全性を実行時に検証
- ガベージコレクションされている
- 複数のプログラミングパラダイムをサポート
    - 構造化(特に手続き型)
    - オブジェクト指向
    - 関数型プログラミング

Pythonの特徴から、アルゴリズムとの相性よさそうです。
では、早速Pythonを駆使し、アルゴリズムのモヤモヤを解消してみましょう。

## 進め方

以下の3ステップ構成で、各種アルゴリズムを解いてみます。

- `問題`の提示
- `解決案`を見つける
- `コード`を書く

## 初回ですので、ソートアルゴリズムを例に

### 問題

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

### 解決案

バブルソートを使用し解決してみます。

- Wikipediaから[バブルソート(bubble sort)](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)
    - 隣り合う要素の大小を比較しながら整列させるソートアルゴリズム
    - 最悪時間計算量はO(n2)と遅いので普段は使いません

- ソートの手順
    - ①1番目と2番目を比較し、順番が逆であれば入れ換える
    - ②次に2番目と3番目を比較し、入れ換える
    - ③最後まで行うと、最後の数だけが最大の数として確定する
    - 確定していない部分に対し、上記①から③を繰り返す。

- アルゴリズムの動作例

※ 結果確定したものは太字で表す

8	4	3	7	6	5	2	1	(初期データ)
4	3	7	6	5	2	1	**8**	(1回目の外側ループ終了時 交換回数:7)
3	4	6	5	2	1	**7	8**	(2回目の外側ループ終了時 交換回数:5)
3	4	5	2	1	**6	7	8**	(3回目の外側ループ終了時 交換回数:3)
3	4	2	1	**5	6	7	8**	(4回目の外側ループ終了時 交換回数:2)
3	2	1	**4	5	6	7	8**	(5回目の外側ループ終了時 交換回数:2)
2	1	**3	4	5	6	7	8**	(6回目の外側ループ終了時 交換回数:2)
**1	2	3	4	5	6	7	8**	(7回目の外側ループ終了時 交換回数:1)

### コード

```bubble_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 bubble_sort(arr):
    if len(arr) == 1:
        return
    yield arr
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1 - i):
            yield arr
            if arr[j] > arr[j + 1]:
                swap(arr, j, 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 = "bubble sort"
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    nums = len(arr)
    algo = bubble_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 bubble_sort.py
```
- 結果
    - ソート過程が可視化されます

![bubble-sort.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/c82f4954-1ab0-0814-e814-94cdfe0964f7.gif)


## おわりに

サンプルとしてバブルソートを解いてみました。
次回から、Pythonを使って各種アルゴリズムを解いていきます。
お楽しみに。

##### [次回] [アルゴリズムのモヤモヤをPythonで解消(2): 挿入ソート](https://qiita.com/mingchun_zhao/items/c9d329cb86cc43c6cde7)