ソートアルゴリズムを実装する (1) 前準備

初めに

何年も前に、本気でアルゴリズムを学習しようと思い立ちアルゴリズムイントロダクションを購入した。
さて、本書を読み始めたは良いが数式を追い切れずに気づけば流し読みになってしまい、実際のアルゴリズムさえ把握できないまま積読本となってしまっている。

というわけで少しずつでも本書を読んで行きたいと思う。
しかし数式を完璧に追いきれるか? と言うとそんなことはない。
そこで、最低限のエッセンスくらいは頭に叩き込んでおくことを目標とし、本書中で紹介されているアルゴリズムをひとつずつ実装して行く。
この際にはできる限り (もちろん自分の理解の範囲となるが) 説明も加える。
ただし、本書中の数学的な話 (アルゴリズムの正当性評価などなど) は読み物程度と捉え、実装に重きを置く。
実装は楽なため Python を用いて行う。いつか気が向けば C とかでもやるかもしれないが、まずないだろう。

実のところ、数ヶ月ほど本格的なコーディングというものを行っていないのでリハビリも兼ねる。
またブログを通じて、体系的な文章を高頻度に作成していくという作業を一度実施してみたいという、ある種の興味もある。
せめて週1くらいで何かしらの更新ができるようにしたいが、これは希望的観測である……いくら滞ったとしても、月1は最低ラインとしたい。
……積読本は他にもたくさんあるため、少なくともしばらくネタには困らなさそうである。

(余談だが、私が初めて購入したアルゴリズムの本はあろうことか、紙面上にあらゆる数式が散りばめられ難解と定評のあるThe Art of Computer Programmingである。
当時の自分は読破できると思っていたのだろうか? 即刻めでたく積読リスト入りした。)

では本題に入ろう。

ソートアルゴリズム

アルゴリズムの代表例と言えばソート (データの並び替え) である。
本書においても初っ端からソートが紹介されている。

例えば、

83, 36, 67, 87, 53, 76, 52, 14, 20, 9

というデータ列を昇順にソートすると、

9, 14, 20, 36, 52, 53, 67, 76, 83, 87

となる。一方で降順であれば

87, 83, 76, 67, 53, 52, 36, 20, 14, 9

である。

Python によるソート処理

大概のプログラミング言語では、ごくごく簡単にソートが行えるようになっている。
Python では次のようにソートを行える。

# ソートするデータ列
lst = [83, 36, 67, 87, 53, 76, 52, 14, 20,  9]

# 昇順にソート
sorted_lst = sorted(lst)
print(sorted_lst)  # [9, 14, 20, 36, 52, 53, 67, 76, 83, 87]

# 降順にソート
sorted_lst = sorted(lst, reverse=True)
print(sorted_lst)  # [87, 83, 76, 67, 53, 52, 36, 20, 14, 9]

ソートアルゴリズムの計算効率

こういったプログラミング言語に組み込み関数として実装されているソートでは、相当に計算効率の良いアルゴリズムが用いられている。
アルゴリズムの計算効率の尺度は、データ列 $n$ の長さが長くなったときの計算量の増加率である。

例えば挿入ソートというアルゴリズムは、 $c_1 n^2$ の計算時間を要する ( $c_1$ は定数) 。
一方でマージソートというアルゴリズムは $c_2 n \log_2 n$ の計算時間を要する ( $c_2$ は定数) 。

どちらのアルゴリズムの効率がよいだろうか?
いずれも定数と $n$ を共通で持っているため除外し、残りの $n$ (挿入ソート) と $\log_2 n$ (マージソート) で計算量の増加率を比較してみよう。
$n$ が大きくなっていくと当然 $\log_2 n$ の増加率は減っていく。
よって計算効率が良いアルゴリズムはマージソートである。

ソートのテスト関数の実装

次回の記事ではまずは挿入ソートを実装する予定である。
ソートアルゴリズムを実装した際、問題がないかテストを行うべきである。
今回は前準備として、テスト関数を実装しよう。

要は実装したソートアルゴリズムにより正しくソートが行われていることが確認できればよい。
組み込み関数という信頼度の高いものがあるので、これをテストとして使用してしまおう。

ソートされているかを判定する is_sorted 関数を次のように実装した。

list への変換
- 引数としてnumpy.ndarrayが与えられるケースを想定し list への変換を行っている。
- numpy.ndarray を比較するとデータの要素ごとの比較となり今回期待する動作ではない。
ソート済みかの判定方法
- 関数は引数で与えられたデータ列が既にソートされていれば、更にソートしても変化しない。
- つまりソート済みということとなる。

ソースコード

def is_sorted(l):
    """リストがソートされているか判定する。

    Args:
        l (list) : 数値のリスト

    Returns :
        sorted (bool) : リストがソートされていれば True, そうでなければ False
    """

    l = list(l) # (1)
    return l == sorted(l) # (2)


if __name__ == "__main__":
    import numpy as np

    l = np.random.randint(2**16, size=10)
    print('ソート前:', is_sorted(l))
    l.sort()
    print('ソート後:', is_sorted(l))