アルゴリズムのモヤモヤをPythonで解消(5): マージソート

---

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

はじめに

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

今回のアルゴリズム: マージソート

問題

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

解決案

マージソートを使用し、解決します。

• Wikipediaからマージソート(merge sort)

  • ボトムアップの分割統治法による、ソートアルゴリズム
    • 大きい列を多数の列に分割し、それぞれマージする
      • 作業を並列化できる
    • 整列済み複数個の列を1個の列にマージする際
      • 小さいものから先に新しい列に並べることで、新しい列も整列される
  • 最悪計算時間: O($n\ log\ {n}$)
  • 最悪空間計算量: O(n)
    • in-placeのバリエーションも提案されている
      • in-placeは、入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない
  • 安定ソートを実装可能
    • 分割と統合の実装に依存
  • クイックソートとの比較
    • クイックソートより、最悪計算時間は少ない
    • ただし、ランダムなデータでは、通常クイックソートが速い

• マージソートの手順

  • 1. データ列を分割(通常、二等分)
  • 2. 分割された各データ列で
    • 含まれるデータが1個の場合、それを返却
    • 2個以上なら、ステップ1から3を再帰的に適用しマージソート
  • 3. 二つのソートされたデータ列(1個であればそれ自身)をマージ

• マージソートの動作例

データ	処理内容
8 4 3 7 6 5 2 1	初期データ
8 4 3 7 | 6 5 2 1	データ列を二分割
8 4 | 3 7 | 6 5 | 2 1	再度二分割
4 8 | 3 7 | 5 6 | 1 2	各データ列のデータ数が2以下となった 各データ列内のデータをソート
3 4 7 8 | 1 2 5 6	右2つのデータ列、左2つのデータ列を それぞれマージ/ソートし 2つのデータ列にする
1 2 3 4 5 6 7 8	2つのデータ列をマージ/ソートし アルゴリズム終了

• マージソート計算量
  • 最悪計算時間: O($n\ log\ {n}$)
  • 最良計算時間
    • 通常: O($n\ log\ {n}$)
    • Natural Variant: O(n)
  • 平均計算時間: O($n\ log\ {n}$)

コード

merge_sort.py

import matplotlib.pyplot as plt
import matplotlib.animation as ani
import matplotlib.cm as cm

def merge(arr, min, mid, max):
    new_arr = []
    i = min
    j = mid + 1
    while i <= mid and j <= max:
        if arr[i] < arr[j]:
            new_arr.append(arr[i])
            i += 1
        else:
            new_arr.append(arr[j])
            j += 1
    if i > mid:
        while j <= max:
            new_arr.append(arr[j])
            j += 1
    else:
        while i <= mid:
            new_arr.append(arr[i])
            i += 1
    for i, val in enumerate(new_arr):
        arr[min + i] = val
        yield arr

def merge_sort(arr, min, max):
    if max <= min:
        return
    elif min < max:
        yield arr
        mid = (min + max) // 2
        yield from merge_sort(arr, min, mid)
        yield from merge_sort(arr, mid + 1, max)
        yield from merge(arr, min, mid, max)
        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 = "merge sort"
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    nums = len(arr)
    algo = merge_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=500, repeat=False)
    mng = plt.get_current_fig_manager()
    mng.full_screen_toggle()
    plt.show()

• matplotlibがインストールされていない場合

$ pip install matplotlib

• 実行

$ python merge_sort.py

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

おわりに

Pythonでマージソートアルゴリズムを解いてみました。
次回も続きます。お楽しみに。

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