Python 3 で数学を。

Python 3 とライブラリで数学の問題を解いていきます。統計学や機械学習はときどき。

アルゴリズム。挿入ソート。Insertion Sort (Python 3)

使用するライブラリ

なし

Python 3 コード

insertion_sort.py

#!/usr/bin/env python3


"""(docstring)
"""


def insertion_sort(A):
    """(docstring)
    """
    # 挿入ソートは、要素数が少ないか、最初から集まりがほぼ整列している場合に使用する。
    # 最良: O(n) 
    # 平均, 最悪: O(n^2)

    for j in range(1, len(A)):
        key = A[j]
        i = j-1
        while i >= 0 and A[i] > key:
            A[i+1] = A[i]
            i -= 1
        A[i+1] = key

    return A


if __name__ == '__main__':
    A1 = [5, 2, 4, 6, 1, 3]
    print(insertion_sort(A1))

    A2 = [2, 4, 6, 1, 3, 5]
    print(insertion_sort(A2))

    A3 = [15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14]
    print(insertion_sort(A3))

出力

$ python3 insertion_sort.py
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

参考文献

アルゴリズムクイックリファレンス 第2版

アルゴリズムクイックリファレンス 第2版

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)