[Python] 挿入ソートの実装方法とアルゴリズム

Pythonと選択ソート

Pythonで挿入ソートを実装してみます。Python3.6を使います。

挿入ソートは、時間計算量 O(n^2) でバブルソートや選択ソートと同じく高速なソートアルゴリズムとは言えません。ただし、挿入ソートについて言えばある面で有用なソートアルゴリズムです。

挿入ソートは要素数の少ないデータに対して、高速に動作する可能性があります。これはクイックソートなど高速なソートアルゴリズムについては、処理のオーバーヘッドが発生するためです。

さらに挿入ソートには、ほぼソート済のデータに対して高速に動作します。これら挿入ソートの特性を生かし、ある程度の範囲まで高速なソートアルゴリズム(クイックソートやマージソート)を利用し、要素数が少なくなった段階で挿入ソートに切り替えるという手法が考えられます。　

以下サンプルソースです。

# 挿入ソート
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        tmp = array[i] # 挿入する値を退避
        if tmp < array[i-1]:
            # 挿入する位置までずらしていく
            j = i
            while True:
                array[j] = array[j-1]
                j -= 1
                if j == 0 or tmp >= array[j-1]:
                    break
            array[j] = tmp # 空いた位置に退避していた値を挿入

# デバッグ
if __name__ == "__main__":
    array = [1,2,3,4,5,3,2,1,4,3,4,5,0]
    print("before", array)
    insertion_sort(array)
    print("after ", array)

挿入ソートのアルゴリズム

挿入ソートは、整列済のデータの適切な位置にデータを挿入しながらソートを行います。まずはソート対象データの先頭要素をソート済(1件だけ)のデータとして考えます。2件目以降のデータから、ソート済のデータの適切な位置に挿入します。

挿入する際、バブルソートのように交換を繰り返しながら適切な位置まで移動させる方法でも実装できますが、余計な交換処理は無駄になってしまいます。よって、一時変数に挿入する値を退避して、適切な位置までデータをずらしながら挿入処理を行います。

参考URL

• 挿入ソート – Algoful
• 挿入ソート – Wikipedia