挿入ソート（＾～＾）

「　挿入ソートって何だぜ？」

「　分かるが、説明するのは　むずかしい」

「　トランプのババ抜きやってて、一番右のカードを　真ん中らへんに入れるやつよ」

「　マンガで描いてくれないと　分からんなあ」

「　👆　５枚のカードを用意しましょう」

「　👆　シャッフルします」

「　これを　A, B, C, D, E　に並び替えなおすのが　ソート（Sort）　なのよ」

「　並び替えりゃ　いいじゃないか」

「　やってみろだぜ」

「　👆　ほら　でけた」

「　きふわらべが　正しい」

「　それよりは　挿入ソート　の方が　高速なのよ」

「　じゃあ　まず　きふわらべソート　を実装しようぜ？　Python　で」

cards = ['C', 'E', 'A', 'D', 'B']

print(f"(1) {cards}")

# in-placeなスワップ と呼ばれる技
temp = cards[2]
cards[2] = cards[1]
cards[1] = cards[0]
cards[0] = temp

print(f"(2) {cards}")

# in-placeなスワップ
temp = cards[4]
cards[4] = cards[3]
cards[3] = cards[2]
cards[2] = cards[1]
cards[1] = temp

print(f"(3) {cards}")

# in-placeなスワップ
temp = cards[4]
cards[4] = cards[3]
cards[3] = temp

print(f"(4) {cards}")

(1) ['C', 'E', 'A', 'D', 'B']
(2) ['A', 'C', 'E', 'D', 'B']
(3) ['A', 'B', 'C', 'E', 'D']
(4) ['A', 'B', 'C', 'D', 'E']

「　👆　こうだぜ」

「　じゃあ　次に　挿入ソート　を見せてくれだぜ」

「　👆　これよね」

「　👆　場所に　０から連番で　数が振ってあって」

「　👆　r　を２番目に置いてみましょう。
ひとまず、今 r 番目にあるカードを　key　と呼ぶとします」

「　👆　r　の１つ左を　l　とします」

「　👆　l が 0 のときは何もせず、key を l+1 の添え字のところに入れます」

「　変わんね」

「　👆　r　が　1　増えます。
key が A になるのと、 l　が　r-1　になるのは、　r　の動きと一緒に　おまとめ　されています」

「　今度は　l　は　0　ではないぜ」

「　👆　そのときは　l　の添え字のところにあるカードも見ます。
l　のカードと、　r　のカードを見比べて、　r　のカードより　l　のカードの方が大きいときは、
並び替えを　これから行います」

「　👆　添え字が　l　のカードを、添え字が　l+1　のところへ上書きします」

「　Aのカードが消えた……」

「　👆　l　が　1　減ります」

「　l　が　0　になると、　l　は　減ろうとするのを止めます」

「　👆　key　を　l+1　の添え字のところに　上書きします」

「　key と l　が　ひっくり返ったな」

「　👆　r　が　ひとつ　大きくなります」

「　👆　D と E はひっくり返っているので、上書きコピーが起こります」

「　👆　l　は　１つ小さくなります」

「　A　と　E　は　ひっくり返っていないので　何も起きません」

「　👆　l+1　の添え字のところに　key　が入ります」

「　そんなん繰り返しても　先頭の　C　が　真ん中にこなくないか？」

「　疑似コードが間違ってんだろ。　もうMITの教科書なんか信用しないぜ。　だいたい　分かったな」

「　本当の　挿入ソート　を知らないんだが」

📖　挿入ソート

「　👆　Wikipedia　にも載ってるわよ」

# [挿入ソート](https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88)
cards = ['C', 'E', 'A', 'D', 'B']

print(f"(1) {cards}")

for i in range(2, len(cards)):
    tmp = cards[i]
    if cards[i-1] > tmp:
        j = i
        while True:
            cards[j] = cards[j-1]
            j -= 1
            if j > 0 and cards[j-1] > tmp:
                pass
            else:
                break
        cards[j] = tmp
    print(f"(2) {cards}")

print(f"(3) {cards}")

(1) ['C', 'E', 'A', 'D', 'B']
(2) ['A', 'C', 'E', 'D', 'B']
(2) ['A', 'C', 'D', 'E', 'B']
(2) ['A', 'B', 'C', 'D', 'E']
(3) ['A', 'B', 'C', 'D', 'E']

「　👆　マシそうだな。　説明してくれだぜ」

「　👆　５つのカードがあるとしましょう」

「　👆　シャッフルします」

「　👆　２番目に　r　を置きます。　添え字が　r　のところにあるカードを　tmp　とします」

「　👆　左隣のカードと比較して、大小関係がひっくり返っていたら、入替処理を始めます」

「　👆　r のところに j を置きます」

「　👆　j-1　の添え字のところにあるカードを、　j　の添え字のところに上書きします」

「　👆　j　を　1　減らします」

「　j　が　0　の添え字のところにあるときは、入替動作を停止します」

「　👆　添え字が　j　のところに、　tmp　のカードを上書きします」

「　そんなところに　E　がくるのは　おかしくないかだぜ！」

「　さっきの　Pythonコードは　結果が正しいしな」

「　分からん」

「　C E　を入れ替えたのが　間違いでは？」

「　そこだぜ」

「　👆　左から順に　揃っていくみたいね」

「　そんなループしてるもんな」

「　揃っているだけで、次の１個が　また挿入されてくるから、確定ではないそうだぜ」

疑似コードの添え字は１から

「　プログラム・チャンネルで質問したら、疑似コードの添え字は　０から始まるのではなく、１から始まるそうよ」

「　わたしからは　出てこない発想だぜ」

# MIT教科書 挿入ソート

# 添え字は 1 から使用
A = [' ', 'E', 'D', 'C', 'B', 'A']

# Start
print(f"(S) {A}")

for j in range(2, len(A)):
    key = A[j]
    # A[j]をソート済みの列 A[1..j-1]に挿入する
    i = j-1
    while i > 0 and A[i] > key:
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key
    print(f"({j}) {A}")

(S) [' ', 'E', 'D', 'C', 'B', 'A']
(2) [' ', 'D', 'E', 'C', 'B', 'A']
(3) [' ', 'C', 'D', 'E', 'B', 'A']
(4) [' ', 'B', 'C', 'D', 'E', 'A']
(5) [' ', 'A', 'B', 'C', 'D', 'E']

「　おー、いけたぜ」

見所とは

「　で、見どころは　どこなんだぜ？」

「　👆　左手と　右手で説明されるみたいだな」

「　👆　で、５枚のカードがあるとき」

「　👆　左端から２枚目を　右手へ、　その左隣を　左手へ　持つのが　初期配置だぜ」

「　右手の方が　偉そうにしてるのね」

「　👆　右手に持ってるのは、　スワップのtmp　だと思ってくれだぜ。
何のことか分からないかもしれないが　ひとまず　そう覚えておけだぜ」

「　👆　極端に色分けすると、　上図の　赤色が　整列されたカード、　緑色が　現在のカード、
水色が　残りのカード　だぜ」

「　👆　これを情報処理では　赤色のカードの添え字を　j-1、　緑色のカードの添え字を　j、
水色のカードの添え字を　j+1 .. n　と言ってるわけだな」

「　そんな言い方されると、ワケ分かんないのよ」

「　👆　赤色のところを　ループ不変式 （loop invariant）と呼ぶらしいぜ」

「　何だぜ　それ？」

「　知らね」

「　プログラミング・チャンネルによると、　ループ不変条件　とでも訳した方がいいもので、
コンパイラから見ると、
ループしている間　ずっと値が変わらないから　ループの外に出してもよくね？
というもの　らしいわよ」

「　分かったような、分からんような」

「　👆　赤い所って、ループ中に　ずっと変わらんの？」

「　これから　緑色のカードを挿入するのだから、途中で　変わるだろ」

「　ループの直前で　いつも変わってないらしいわよ」

「　緑色のカードを挿入したら　変わるだろ」

「　フーム。　なんか　ループの前判定の条件文　のことを　ループ不変式（loop invariant）と呼んでる気がするな」

「　右手の１枚のカードを　左手のカードの束に挿入しようとするとき、左手のカードの束は整列済みだ、
ということを　言ってる気がするぜ」

ループ不変式に再挑戦

「　プログラミング・チャンネルによると、 ループ不変式 というのは、
ループの前、
ループの最中の末尾、
ループの後、
この３つの　どこを取っても　条件式が真であることが　崩れないような、条件式らしいぜ」

「　プログラミング・チャンネルが　記事を書いてくれだぜ。お父んは黙れ」

「　ループの最中に　緑色のカードを挿入したら　整列していない状態が　一時的にできるんじゃないの？」

「　調べてみると　整列していない状態は　一時的にも出てこなかった。説明しよう」

B, C, D, A
↓
B, C, D, D
↓
B, C, C, D
↓
B, B, C, D
↓
A, B, C, D

「　👆　何週目のループでも、ソートされた状態だぜ」

「　同じカードが２枚被っていて　Aが無い状態でも　整列されている　と言っていいのかだぜ？」

「　変わってるよな」

「　プログラミング・チャンネルによると……」

「　またきた」

「　ラーメン食べ郎が言っている　同じカードが２枚被っている　とか、　Aが無い　という状態は
気にすると　何も言えなくなるから、
コンピューター・サイエンスでは　何か言えるところ　だけを言うようよ。
前者が　強い条件、　後者が　弱い条件」

「　フーム」

「　弱い条件の方が　コンピューター・サイエンスに出てくるのよ」

「　フーム」