『Pythonで体験してわかるアルゴリズムとデータ構造』メモその3/挿入ソートのイメージをつかむ

『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

第4章 アルゴリズムを思い受ける方法

書籍中では挿入ソートをベースに説明されている。

この章のゴールは 自分でアルゴリズムを思いつくためにはどのようなものを参考にすればよいか

挿入ソートについて

整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。

バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。
挿入ソート - Wikipedia

挿入ソートのイメージは以下

実装

def insertion_sort(array):
    n = len(array)
    
    for i in range(1, n):
        print("{}回目処理".format(str(i)))
        tmp = array[i]
        print("処理対象：", tmp)
        if tmp < array[i-1]:
            # 挿入する位置までずらしていく
            j = i
            while True:
                array[j] = array[j-1]
                print("{}を{}番目に移動：{}".format(array[j-1], j+1, array))
                j -= 1
                # 配列の先頭に到達するか、前の配列値が小さい場合、次の処理へ
                if j == 0 or tmp >= array[j-1]:
                    break
            array[j] = tmp
            print("{}を{}番目に移動：{}".format(tmp, j+1, array))
        print("確定：", array)
        print("")

array = [1,2,3,4,5,3,2,1,3,0]
print("処理前：", array)
print("")
insertion_sort(array)
print("処理後 ", array)

処理前： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0]

1回目処理
処理対象： 2
確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0]

2回目処理
処理対象： 3
確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0]

3回目処理
処理対象： 4
確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0]

4回目処理
処理対象： 5
確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0]

5回目処理
処理対象： 3
5を6番目に移動：[1, 2, 3, 4, 5, 5, 2, 1, 3, 0]
4を5番目に移動：[1, 2, 3, 4, 4, 5, 2, 1, 3, 0]
3を4番目に移動：[1, 2, 3, 3, 4, 5, 2, 1, 3, 0]
確定： [1, 2, 3, 3, 4, 5, 2, 1, 3, 0]

6回目処理
処理対象： 2
5を7番目に移動：[1, 2, 3, 3, 4, 5, 5, 1, 3, 0]
4を6番目に移動：[1, 2, 3, 3, 4, 4, 5, 1, 3, 0]
3を5番目に移動：[1, 2, 3, 3, 3, 4, 5, 1, 3, 0]
3を4番目に移動：[1, 2, 3, 3, 3, 4, 5, 1, 3, 0]
2を3番目に移動：[1, 2, 2, 3, 3, 4, 5, 1, 3, 0]
確定： [1, 2, 2, 3, 3, 4, 5, 1, 3, 0]

7回目処理
処理対象： 1
5を8番目に移動：[1, 2, 2, 3, 3, 4, 5, 5, 3, 0]
4を7番目に移動：[1, 2, 2, 3, 3, 4, 4, 5, 3, 0]
3を6番目に移動：[1, 2, 2, 3, 3, 3, 4, 5, 3, 0]
3を5番目に移動：[1, 2, 2, 3, 3, 3, 4, 5, 3, 0]
2を4番目に移動：[1, 2, 2, 2, 3, 3, 4, 5, 3, 0]
2を3番目に移動：[1, 2, 2, 2, 3, 3, 4, 5, 3, 0]
1を2番目に移動：[1, 1, 2, 2, 3, 3, 4, 5, 3, 0]
確定： [1, 1, 2, 2, 3, 3, 4, 5, 3, 0]

8回目処理
処理対象： 3
5を9番目に移動：[1, 1, 2, 2, 3, 3, 4, 5, 5, 0]
4を8番目に移動：[1, 1, 2, 2, 3, 3, 4, 4, 5, 0]
3を7番目に移動：[1, 1, 2, 2, 3, 3, 3, 4, 5, 0]
確定： [1, 1, 2, 2, 3, 3, 3, 4, 5, 0]

9回目処理
処理対象： 0
5を10番目に移動：[1, 1, 2, 2, 3, 3, 3, 4, 5, 5]
4を9番目に移動：[1, 1, 2, 2, 3, 3, 3, 4, 4, 5]
3を8番目に移動：[1, 1, 2, 2, 3, 3, 3, 3, 4, 5]
3を7番目に移動：[1, 1, 2, 2, 3, 3, 3, 3, 4, 5]
3を6番目に移動：[1, 1, 2, 2, 3, 3, 3, 3, 4, 5]
2を5番目に移動：[1, 1, 2, 2, 2, 3, 3, 3, 4, 5]
2を4番目に移動：[1, 1, 2, 2, 2, 3, 3, 3, 4, 5]
1を3番目に移動：[1, 1, 1, 2, 2, 3, 3, 3, 4, 5]
1を2番目に移動：[1, 1, 1, 2, 2, 3, 3, 3, 4, 5]
0を1番目に移動：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5]
確定： [0, 1, 1, 2, 2, 3, 3, 3, 4, 5]

処理後  [0, 1, 1, 2, 2, 3, 3, 3, 4, 5]