今日から
INTRODUCTION TO ALGORITHMSを読み始めたので、簡単な内容も多いですが、アルゴリズムをまとめていきます。

挿入ソート

要素数10の配列を挿入ソートによってソートするのは、次の例と類似しています。

テーブルに10枚のトランプが置かれていて、初め手札の枚数は0とします。テーブルのカードを一枚ずつ引いていき、手札に加えるのですが、手札は常に昇順にソートされた状態にキープします。手札って整頓させておきたいですよね、左に数字の小さいカード、右に数字の大きいカードというように。
このプロセスのポイントは、カードが三つに分類できるということです。

• 手札にある既にソートされたカード
• 今テーブルから引いて、これから加えようとしているカード
• まだテーブルに置かれているカード

挿入ソートもこのことに着目します。

• 配列のうち、既に昇順にソートされている部分
• 配列のうち、今見ている要素
• 配列のうち、まだ昇順にソートされていない部分

例えば、

インデックス	0	1	2	3	4	5	6	7	8	9
値	5	3	8	1	2	4	7	6	9	0

という要素数10の配列があるとします。まだテーブルに全てのカードが置かれている状態と考えてください。
カードを一枚ずつ引いていって、今ちょうど5枚目を引いたとします。これは、配列がインデックス0-3まではソートされていて、今インデックス4の2に着目していることに等しいです。

インデックス	0	1	2	3	4	5	6	7	8	9
値	1	3	5	8	2	4	7	6	9	0

さて、この2を挿入する位置探しましょう。

• 2と8を比べ、8の方が大きいので、2と8の位置を交換します。
• 2と5を比べ、5の方が大きいので、2と5の位置を交換します。
• 2と3を比べ、3の方が大きいので、2と3の位置を交換します。
• 2と1を比べ、2の方が大きいので、ここで終了します。

同様の手順を、6番目から10番目のカードに対しても行うと、ソートされた配列が得られます。これが挿入ソートの手順です。

def insertion_sort(a) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while key < a[j] and j >= 0:
            a[j+1] = a[j] 
            j -= 1
        a[j+1] = key

a = [1, 3, 5, 8, 2, 4, 7, 6, 9, 0]
insertion_sort(a)
print(a)

出力

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

冒頭でご紹介したテキストですが、何で挿入ソートでこんなにページ割けるんだってくらい、一つのアルゴリズムに関して色々説明しているので、読み進めて補足することがあれば別記事をまた書こうと思います。