マージ・ソート(^~^)

しゅるんしゅるん(^~^) 公開下書き

20210124shogi2a2b1.png
「 挿入ソートは さっぱり分からなかったな」

kifuwarabe-futsu.png
「 分からないのに 先に進むから また 分からない になる」

ohkina-hiyoko-futsu.png
「 そんときゃ 戻りゃいいのよ」

ramen-tabero-futsu2.png
「 次は マージ・ソート だが、説明読んでも さっぱり分からないぜ。
疑似コードでも 読むかな」

# [マージソート](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88)


def merge(cards, space, l_begin, mid, r_end):
    """
    cards : str[int]
        全部のカード。並び替えたい
    space : str[int]
        並び替えのために使う一時的なスペース。カードが全部入るだけのサイズがある
    l_begin : int
        左端。左側のスタート地点(^~^)
    mid : int
        真ん中。この数を含まない範囲で左から l が寄ってくる(^~^)右側のスタート地点でもある(^~^)
    r_end : int
        右端。この数を含まない範囲で左から r が寄ってくる(^~^)
    """
    l = l_begin
    r = mid

    # スワップ・スペースの配列の添え字
    s = 0

    # l も r も端を超えてなければ
    while l < mid and r < r_end:
        # 右側の方が小さい(か等しい)なら
        if cards[l] <= cards[r]:
            # 右側の方をスワップ・スペースの方へ移す
            space[s] = cards[l]
            l += 1
            s += 1
        else:
            # 左側の方
            space[s] = cards[r]
            r += 1
            s += 1

    if l == mid:  # 左側をスワップ・スペースに移動し尽くしたので、右側も順番にスワップ・スペースに入れていく
        while r < r_end:
            space[s] = cards[r]
            r += 1
            s += 1
    else:
        while l < mid:  # 左側の方
            space[s] = cards[l]
            l += 1
            s += 1

    # スワップ・スペースの内容を cards に戻す
    for s2 in range(0, s):
        cards[l_begin + s2] = space[s2]


def merge_sort(cards, space, l_begin, r_end):
    """左と右をマージ(^~^)"""

    # 0~1枚のカードを指してるようなら再帰を停止
    if l_begin == r_end or l_begin == r_end - 1:  # Base case
        return

    # 真ん中
    mid = (l_begin + r_end) // 2  # 小数点以下切り捨て(^~^)

    merge_sort(cards, space, l_begin, mid)
    merge_sort(cards, space, mid, r_end)
    merge(cards, space, l_begin, mid, r_end)

    # 途中結果(または最終結果)表示(^~^)
    print_all_cards(cards, l_begin, mid, r_end)


def print_all_cards(cards, l_begin, mid, r_end):
    """カードの表示"""
    begin_all = 0
    end_all = len(cards)
    for i in range(begin_all, end_all):
        if i == l_begin:
            print(" [ ", end='')
        elif i == mid:
            print(" | ", end='')
        elif i == r_end:
            print(" ] ", end='')
        print(f"{cards[i]} ", end='')

    if end_all == mid:
        print(" | ", end='')
    if end_all == r_end:
        print(" ] ", end='')

    print("")  # New line


def main():
    # 全部のカード
    cards = ['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
    # スワップ・スペース。とりあえず配列のサイズを確保しとく
    space = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']

    l_begin = 0  # 左端
    r_end = len(cards)  # 右端

    # 初期配置表示(^~^)
    print_all_cards(cards, l_begin, r_end, r_end)

    merge_sort(cards, space, l_begin, r_end)


main()
 [ J I H G F E D C B A  |  ] 
 [ I  | J  ] H G F E D C B A
I J H  [ F  | G  ] E D C B A
I J  [ F  | G H  ] E D C B A
 [ F G  | H I J  ] E D C B A
F G H I J  [ D  | E  ] C B A
F G H I J D E C  [ A  | B  ]
F G H I J D E  [ A  | B C  ]
F G H I J  [ A B  | C D E  ] 
 [ A B C D E  | F G H I J  ]

ramen-tabero-futsu2.png
「 👆 分かったけど 説明が大変だな。どうすっかな」

20210701coder1.png

ohkina-hiyoko-futsu.png
「 👆 カードが10枚 あんのよ」

20210701coder1a0.png

ramen-tabero-futsu2.png
「 👆 とりあえず 初期配置を 逆順にしようぜ。
これを マージ・ソートを使って 元通りに並び替えようぜ」

20210701coder1a1.png

ramen-tabero-futsu2.png
「 👆 最初は 二分割するんだぜ。これを カードが1枚になって分割できなくなるまで やれだぜ」

kifuwarabe-futsu.png
「 分かったぜ」

20210701coder1a2.png

kifuwarabe-futsu.png
「 👆 (S+E) / 2 で小数点切り捨てだな」

ohkina-hiyoko-futsu.png
「 真ん中って そんなとこかなあ?」

20210701coder1a3.png

kifuwarabe-futsu.png
「 👆 どんどん 分割していこうぜ」

20210701coder1a4.png

kifuwarabe-futsu.png
「 👆 分割は ここで停止だぜ」

ohkina-hiyoko-futsu.png
「 分割って 必ず停止すんの?」

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

20210701coder2.png

ramen-tabero-futsu2.png
「 👆 次は 分割したものを まとめていけだぜ」

kifuwarabe-futsu.png
「 せっかく 分割したのに……。なんで そんなことを」

20210701coder2a1.png

ramen-tabero-futsu2.png
「 👆 マージするとき、整列させとけだぜ」

20210701coder2a2.png

ramen-tabero-futsu2.png
「 👆 マージしたカードのまとまりが、整列されているということが重要なんだぜ」

kifuwarabe-futsu.png
「 わかった、わかった」

20210701coder2a3.png

ramen-tabero-futsu2.png
「 👆 だから何なのか、と思うが どこを見ても マージされたカードのまとまりは、整列されているな!」

ohkina-hiyoko-futsu.png
「 わかった、わかった」

20210701coder2a4.png

ramen-tabero-futsu2.png
「 👆 初期配置に戻ってきたら、整列されているぜ」

ohkina-hiyoko-futsu.png
「 フーン」

何度でもクリック!→

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

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

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

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

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

ボードとは?

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