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

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

## はじめに

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

## 今回登場するアルゴリズム: クイックソート

### 問題

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

### 解決案

クイックソートを使用し、解決します。

- Wikipediaから[クイックソート(quicksort)](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)
    - ソートアルゴリズムで、分割統治法の一種
    - 分割統治法とは、以下の問題解決手法
        - そのままでは解決できない大きな問題を
        - 小さな問題に分割し、その全てを解決
        - 最終的に最初の問題全体を解決

- 計算量
    - 最悪計算時間: O($n^{2}$)
    - 最良計算時間: O($n\ log\ n$)
    - 平均計算時間: O($n\ log\ n$)

- ソートの手順
    - 1\. ピボット選択
        - 適当な値(ピボット)を境界値として選択
    - 2\. 配列分割
        - ピボット未満の要素を配列の先頭側に集める
        - ピボット未満の要素のみを含む区間とそれ以外に分割
    - 3\. 再帰
        - 分割された区間に対し、再びピボットの選択と分割を行う
    - 4\. ソート終了
        - 分割区間が整列済みなら再帰を打ち切る

- 2\. 配列分割の方法例
    - ①配列要素からピボット`P`を選ぶ
    - ②配列の先頭(左側)から順に、値が`P`以上の要素を探索
        - その位置`LO`を記憶
    - ③配列の終端(右側)から逆順に、値がP未満の要素を探索
        - その位置`HI`を記憶
    - ④`LO`、`HI`について
        - `LO`が`HI`より左にあるなら
            - `LO`にある要素と`HI`にある要素の位置を入れ替え
            - それぞれ`LO`、`HI`の次の要素から手順②、③の探索を再開
        - さもなければ(`LO`が`HI`より右か同じ位置にある)
            - `HI`を境界とし、配列を分割

- アルゴリズムの動作例
    - ピボットの選択方法
        - 探索領域の終端要素をピボットとして選択
    - ※ ピボットを太文字で表す
    - ※ 確定済み領域は取消し線を引く

|数列|探索領域|ピボット|処理内容|
|--|--|--|--|
|8 4 3 7 6 5 2 **1**|[8 - 1]|1|1の左から1以上を探索し8<br>1より大きいため入替え|
|**1** 4 3 7 6 5 2 8|[4 - 8]|1|1の右から1未満を探索し存在しない<br>1の右で分割、[1]領域は終了|
|~~1~~ \| 4 3 7 6 5 2 **8**|[4 - 8]|8|8の左から8以上を探索し存在しない<br>8の左で分割<br>[8]領域は終了|
|~~1~~ \| 4 3 7 6 5 **2** \| ~~8~~ |[4 - 2]|2|2の左から2以上を探索し4<br>2より大きいため入替え|
|~~1~~ \| **2** 3 7 6 5 4 \| ~~8~~ |[2 - 4]|2|2の右から2未満を探索し存在しない<br>2の右で分割<br>[2]領域は終了|
|~~1~~ \| ~~2~~ \| 3 7 6 5 **4** \| ~~8~~ |[3 - 4]|4|4の左から4以上を探索し7<br>4より大きいため入替|
|~~1~~ \| ~~2~~ \| 3 **4** 6 5 7 \| ~~8~~ |[3 - 7]|4|4の左から4以上を探索し存在しない<br>4の右から4未満を探索し存在しない<br>4の右で分割<br>[3,4]領域は終了|
|~~1~~ \| ~~2~~ \| ~~3~~ \| ~~4~~ \| 6 5 **7** \| ~~8~~ |[6 - 7]|7|7の左から7以上を探索し存在しない<br>7の左で分割<br>[7]領域は終了|
|~~1~~ \| ~~2~~ \| ~~3~~ \| ~~4~~ \| 6 **5** \| ~~7~~ \| ~~8~~ |[6 5]|5|5の左から5以上を探索し6<br>5より大きいため入替え|
|~~1~~ \| ~~2~~ \| ~~3~~ \| ~~4~~ \| **5** 6 \| ~~7~~ \| ~~8~~ |[5 6]|5|5の右から5未満を探索し存在しない<br>5の右で分割<br>[5]領域は終了|
|~~1~~ \| ~~2~~ \| ~~3~~ \| ~~4~~ \| ~~5~~ \| **6** \| ~~7~~ \| ~~8~~ |[6]|6|[6]領域は終了|
|~~1~~ \| ~~2~~ \| ~~3~~ \| ~~4~~ \| ~~5~~ \| ~~6~~ \| ~~7~~ \| ~~8~~ |||ソート終了|

### コード

```quick_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 quick_sort(arr, left, right):
    if left >= right:
        return
    pivot = arr[right]
    cur_idx = left
    yield arr
    for i in range(left, right):
        yield arr
        if arr[i] < pivot:
            if i != cur_idx:
                swap(arr, i, cur_idx)
            cur_idx += 1
    if right != cur_idx:
        swap(arr, right, cur_idx)
    yield arr

    yield from quick_sort(arr, left, cur_idx - 1)
    yield from quick_sort(arr, cur_idx + 1, right)

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 = "quick sort"
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    nums = len(arr)
    algo = quick_sort(arr, 0, nums - 1)
    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 quick_sort.py
```
- 結果
    - ソート過程が可視化されます

![quick_sort.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/341a8dac-c479-6e27-15a2-f50f57709942.gif)

## おわりに

Pythonで`クイックソート`アルゴリズムを解いてみました。
一般的な`分割統治法`の考え方も理解できました。
次回も続きます。お楽しみに。

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