はじめに

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

正解を見つける、がゴールでなく、
考える力を身につける、をゴールとしたいです。

3つ以上解き方を見つける
そこからベスト解を選ぶ

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

アルゴリズムの定義

JIS X 0001:1994による定義

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

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

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

アルゴリズムの分類

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

改めて、Pythonとは

WikipediaからPythonとは

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

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

進め方

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

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

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

問題

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

解決案

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

Wikipediaからバブルソート(bubble sort)
- 隣り合う要素の大小を比較しながら整列させるソートアルゴリズム
- 最悪時間計算量は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

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

おわりに

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

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