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

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

はじめに

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

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

問題

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

解決案

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

• Wikipediaからクイックソート(quicksort)

  • ソートアルゴリズムで、分割統治法の一種
  • 分割統治法とは、以下の問題解決手法
    • そのままでは解決できない大きな問題を
    • 小さな問題に分割し、その全てを解決
    • 最終的に最初の問題全体を解決

• 計算量

  • 最悪計算時間: 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 1より大きいため入替え
1 4 3 7 6 5 2 8	[4 - 8]	1	1の右から1未満を探索し存在しない 1の右で分割、[1]領域は終了
1 | 4 3 7 6 5 2 8	[4 - 8]	8	8の左から8以上を探索し存在しない 8の左で分割 [8]領域は終了
1 | 4 3 7 6 5 2 | 8	[4 - 2]	2	2の左から2以上を探索し4 2より大きいため入替え
1 | 2 3 7 6 5 4 | 8	[2 - 4]	2	2の右から2未満を探索し存在しない 2の右で分割 [2]領域は終了
1 | 2 | 3 7 6 5 4 | 8	[3 - 4]	4	4の左から4以上を探索し7 4より大きいため入替
1 | 2 | 3 4 6 5 7 | 8	[3 - 7]	4	4の左から4以上を探索し存在しない 4の右から4未満を探索し存在しない 4の右で分割 [3,4]領域は終了
1 | 2 | 3 | 4 | 6 5 7 | 8	[6 - 7]	7	7の左から7以上を探索し存在しない 7の左で分割 [7]領域は終了
1 | 2 | 3 | 4 | 6 5 | 7 | 8	[6 5]	5	5の左から5以上を探索し6 5より大きいため入替え
1 | 2 | 3 | 4 | 5 6 | 7 | 8	[5 6]	5	5の右から5未満を探索し存在しない 5の右で分割 [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

• 結果
  • ソート過程が可視化されます

おわりに

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

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