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

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

はじめに

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

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

問題

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

解決案

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

• Wikipediaから選択ソート(selection sort)

  • ソートアルゴリズムの一つ
  • 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える
  • 最悪時間計算量は 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

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

おわりに

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

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