Pythonでソートアルゴリズムの学習（選択法、挿入法）

概要

ソートアルゴリズムをPythonで実装し、実行時間を比較する。今回は選択法と挿入法。

結果

実装方法ごとの実行時間の比較。（秒）

要素数	sorted()	選択法	挿入法
100	2e-05	0.000606	0.001208
1,000	0.000119	0.038934	0.093773
10,000	0.001208	3.76022	9.319597
100,000	0.018146	497.49116	974.268513

計測は１度しかやっていなかったり、手元のノートPCで別の作業をしながら計測しているので、あくまで参考程度で。

考察

• 選択法、挿入法は要素数が10倍になると、実行時間はおよそ100倍
• 選択法と比べて挿入法が遅いのは、おそらく実装方法によるもの
• sorted()は高速

プログラム

def swap(list_, x, y):
    """
    リストの要素を交換するユーティリティメソッド
    引数のリストを直接書き換える

    :param list_: リスト
    :param x: 交換するリストの添字
    :param y: 交換するリストの添字
    """
    list_[y], list_[x] = list_[x], list_[y]


def selection_sort(list_):
    """
    選択法を用いてリストをソートする

    リストの先頭から、最小値を探して先頭と入れ替える
    次は2要素目から最小値を探して、それと2要素目を入れ替える
    これを繰り返す。
    """

    length = len(list_)
    for i in range(length - 1):
        min_ = i
        for j in range(i + 1, length):
            if list_[j] < list_[min_]:
                min_ = j
        swap(list_, i, min_)
    return list_


def insertion_sort(list_):
    """
    挿入法を用いてリストをソートする
    """
    length = len(list_)
    for i in range(length):
        j = i
        # 番兵を使えばj>0のチェックが不要になる
        while (list_[j - 1] > list_[j]) and (j > 0):
            swap(list_, j - 1, j)
            j -= 1
    return list_


def generate_random_list(n):
    import random
    return random.sample(list(range(n)), k=n)


def get_process_time(func, *args, **kwargs):
    from datetime import datetime
    start = datetime.now()
    func(*args, **kwargs)
    return (datetime.now() - start).total_seconds()


def main():
    for length in [10 ** 2, 10 ** 3, 10 ** 4, 10 ** 5]:
        l = generate_random_list(length)
        print((get_process_time(sorted, l[:])))
        print(get_process_time(selection_sort, l[:]))
        print(get_process_time(insertion_sort, l[:]))


if __name__ == '__main__':
    main()