挿入ソート(^~^)

へばちゅ(^~^) 公開下書き

20210124shogi2a2b1.png
「 挿入ソートって何だぜ?」

kifuwarabe-futsu.png
「 分かるが、説明するのは むずかしい」

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

ramen-tabero-futsu2.png
「 マンガで描いてくれないと 分からんなあ」

20210630coder45.png

ohkina-hiyoko-futsu.png
「 👆 5枚のカードを用意しましょう」

20210630coder45a1.png

ohkina-hiyoko-futsu.png
「 👆 シャッフルします」

ohkina-hiyoko-futsu.png
「 これを A, B, C, D, E に並び替えなおすのが ソート(Sort) なのよ」

kifuwarabe-futsu.png
「 並び替えりゃ いいじゃないか」

ramen-tabero-futsu2.png
「 やってみろだぜ」

20210630coder45a1.png

kifuwarabe-futsu.png
「 👆 ほら でけた」

ramen-tabero-futsu2.png
「 きふわらべが 正しい」

ohkina-hiyoko-futsu.png
「 それよりは 挿入ソート の方が 高速なのよ」

ramen-tabero-futsu2.png
「 じゃあ まず きふわらべソート を実装しようぜ? 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']

kifuwarabe-futsu.png
「 👆 こうだぜ」

ramen-tabero-futsu2.png
「 じゃあ 次に 挿入ソート を見せてくれだぜ」

20210630coder47.png

ohkina-hiyoko-futsu.png
「 👆 これよね」

20210630coder46.png

ohkina-hiyoko-futsu.png
「 👆 場所に 0から連番で 数が振ってあって」

20210630coder46a1.png

ohkina-hiyoko-futsu.png
「 👆 r を2番目に置いてみましょう。
ひとまず、今 r 番目にあるカードを key と呼ぶとします」

20210630coder46a2.png

ohkina-hiyoko-futsu.png
「 👆 r の1つ左を l とします」

20210630coder46a3.png

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

kifuwarabe-futsu.png
「 変わんね」

20210630coder46a4.png

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

kifuwarabe-futsu.png
「 今度は l は 0 ではないぜ」

20210630coder46a5.png

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

20210630coder46a6.png

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

kifuwarabe-futsu.png
「 Aのカードが消えた……」

20210630coder46a7.png

ohkina-hiyoko-futsu.png
「 👆 l が 1 減ります」

ohkina-hiyoko-futsu.png
「 l が 0 になると、 l は 減ろうとするのを止めます」

20210630coder46a8.png

ohkina-hiyoko-futsu.png
「 👆 key を l+1 の添え字のところに 上書きします」

ramen-tabero-futsu2.png
「 key と l が ひっくり返ったな」

20210630coder46a9.png

ohkina-hiyoko-futsu.png
「 👆 r が ひとつ 大きくなります」

20210630coder46a10.png

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

20210630coder46a11.png

ohkina-hiyoko-futsu.png
「 👆 l は 1つ小さくなります」

ohkina-hiyoko-futsu.png
「 A と E は ひっくり返っていないので 何も起きません」

20210630coder46a12.png

ohkina-hiyoko-futsu.png
「 👆 l+1 の添え字のところに key が入ります」

kifuwarabe-futsu.png
「 そんなん繰り返しても 先頭の C が 真ん中にこなくないか?」

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

kifuwarabe-futsu.png
「 本当の 挿入ソート を知らないんだが」

📖 挿入ソート

ohkina-hiyoko-futsu.png
「 👆 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']

kifuwarabe-futsu.png
「 👆 マシそうだな。 説明してくれだぜ」

20210630coder45.png

ohkina-hiyoko-futsu.png
「 👆 5つのカードがあるとしましょう」

20210630coder46.png

ohkina-hiyoko-futsu.png
「 👆 シャッフルします」

20210630coder48.png

ohkina-hiyoko-futsu.png
「 👆 2番目に r を置きます。 添え字が r のところにあるカードを tmp とします」

20210630coder48a1.png

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

20210630coder48a2.png

ohkina-hiyoko-futsu.png
「 👆 r のところに j を置きます」

20210630coder48a3.png

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

20210630coder48a4.png

ohkina-hiyoko-futsu.png
「 👆 j を 1 減らします」

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

20210630coder48a5.png

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

kifuwarabe-futsu.png
「 そんなところに E がくるのは おかしくないかだぜ!」

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

ramen-tabero-futsu2.png
「 分からん」

kifuwarabe-futsu.png
「 C E を入れ替えたのが 間違いでは?」

ramen-tabero-futsu2.png
「 そこだぜ」

20210630coder49.png

ohkina-hiyoko-futsu.png
「 👆 左から順に 揃っていくみたいね」

ramen-tabero-futsu2.png
「 そんなループしてるもんな」

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

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

ohkina-hiyoko-futsu.png
「 プログラム・チャンネルで質問したら、疑似コードの添え字は 0から始まるのではなく、1から始まるそうよ」

ramen-tabero-futsu2.png
「 わたしからは 出てこない発想だぜ」

# 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']

ramen-tabero-futsu2.png
「 おー、いけたぜ」

見所とは

kifuwarabe-futsu.png
「 で、見どころは どこなんだぜ?」

20210630coder50.png

ramen-tabero-futsu2.png
「 👆 左手と 右手で説明されるみたいだな」

20210630coder50a1.png

ramen-tabero-futsu2.png
「 👆 で、5枚のカードがあるとき」

20210630coder50a2.png

ramen-tabero-futsu2.png
「 👆 左端から2枚目を 右手へ、 その左隣を 左手へ 持つのが 初期配置だぜ」

ohkina-hiyoko-futsu.png
「 右手の方が 偉そうにしてるのね」

20210630coder50a3.png

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

20210630coder50a4.png

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

20210630coder50a5.png

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

ohkina-hiyoko-futsu.png
「 そんな言い方されると、ワケ分かんないのよ」

ramen-tabero-futsu2.png
「 👆 赤色のところを ループ不変式 (loop invariant)と呼ぶらしいぜ」

kifuwarabe-futsu.png
「 何だぜ それ?」

ramen-tabero-futsu2.png
「 知らね」

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

ramen-tabero-futsu2.png
「 分かったような、分からんような」

20210630coder50a6.png

ramen-tabero-futsu2.png
「 👆 赤い所って、ループ中に ずっと変わらんの?」

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

ohkina-hiyoko-futsu.png
「 ループの直前で いつも変わってないらしいわよ」

kifuwarabe-futsu.png
「 緑色のカードを挿入したら 変わるだろ」

ramen-tabero-futsu2.png
「 フーム。 なんか ループの前判定の条件文 のことを ループ不変式(loop invariant)と呼んでる気がするな」

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

ループ不変式に再挑戦

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

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

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

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

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

ramen-tabero-futsu2.png
「 👆 何週目のループでも、ソートされた状態だぜ」

kifuwarabe-futsu.png
「 同じカードが2枚被っていて Aが無い状態でも 整列されている と言っていいのかだぜ?」

ramen-tabero-futsu2.png
「 変わってるよな」

ohkina-hiyoko-futsu.png
「 プログラミング・チャンネルによると……」

kifuwarabe-futsu.png
「 またきた」

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

ramen-tabero-futsu2.png
「 フーム」

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

ramen-tabero-futsu2.png
「 フーム」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事