見出し画像

間違いあり！ 独学コンピューターサイエンティスト 第１部 第４章 p95 の指摘について

🥚𝓗𝓊𝓂𝓅𝓉𝓎𝓓𝓊𝓂𝓅𝓉𝓎𐇬🐾時々にゃん!ฅ(^•ω•*^ฅ

以下のツイートは、独学コンピューターサイエンティスト監訳者の清水川貴之さんへ向けてのものです。

ケツカッチンで、急いで斜め読みしてる途中で見つけたものなので、検証してみました。

検証の為に、p87 のマージソートサンプルプログラム の一部を変更しました。指摘した部分の各値とマージソート関数を呼び出す箇所を追加しています。

以下が、その変更を加えたサンプルプログラムと出力結果です。

def merge_sort(a_list):
    if len(a_list) > 1:
        mid = len(a_list) // 2
        left = a_list[:mid]  # 修正前: left_half
        right = a_list[mid:]  # 修正前: right_half
        merge_sort(left)
        merge_sort(right)

        left_i = 0  # 修正前: left_ind
        right_i = 0  # 修正前: right_ind
        alist_i = 0  # 修正前: alias_ind
        while (
            left_i < len(left) and
            right_i < len(right)
        ):
            if left[left_i] <= right[right_i]:
                a_list[alist_i] = left[left_i]
                left_i += 1
            else:
                a_list[alist_i] = right[right_i]
                right_i += 1
            alist_i += 1
        
        # 検証の為、以下の print文を追加！
        print('    while ( left_i < len(left) and right_i < len(right): ループ後の値！')
        print('    left_i  =', left_i, '  len(left)  =', len(left),
            '  left_i  が len(left)  より大きくなることはない')       
        print('    right_i =', right_i, '  len(right) =', len(right),
            '  right_i が len(right) より大きくなることはない', end='\n\n')

        while left_i < len(left):
            a_list[alist_i] = left[left_i]
            left_i += 1
            alist_i += 1

        while right_i < len(right):
            a_list[alist_i] = right[right_i]
            right_i += 1
            alist_i += 1
    return a_list
    
# merge_sort関数を実行するために以下を追加！
list = [6, 3, 9, 4, 1, 10, 3]  # ソートされるリスト
print('ソート結果！', list, '=>', merge_sort(list[:]))


出力結果


    while ( left_i < len(left) and right_i < len(right): ループ後の値！
    left_i  = 1   len(left)  = 1   left_i  が len(left)  より大きくなることはない
    right_i = 0   len(right) = 1   right_i が len(right) より大きくなることはない

    while ( left_i < len(left) and right_i < len(right): ループ後の値！
    left_i  = 1   len(left)  = 1   left_i  が len(left)  より大きくなることはない
    right_i = 1   len(right) = 2   right_i が len(right) より大きくなることはない

    while ( left_i < len(left) and right_i < len(right): ループ後の値！
    left_i  = 0   len(left)  = 1   left_i  が len(left)  より大きくなることはない
    right_i = 1   len(right) = 1   right_i が len(right) より大きくなることはない

    while ( left_i < len(left) and right_i < len(right): ループ後の値！
    left_i  = 0   len(left)  = 1   left_i  が len(left)  より大きくなることはない
    right_i = 1   len(right) = 1   right_i が len(right) より大きくなることはない

    while ( left_i < len(left) and right_i < len(right): ループ後の値！
    left_i  = 2   len(left)  = 2   left_i  が len(left)  より大きくなることはない
    right_i = 1   len(right) = 2   right_i が len(right) より大きくなることはない

    while ( left_i < len(left) and right_i < len(right): ループ後の値！
    left_i  = 3   len(left)  = 3   left_i  が len(left)  より大きくなることはない
    right_i = 3   len(right) = 4   right_i が len(right) より大きくなることはない

ソート結果！ [6, 3, 9, 4, 1, 10, 3] => [1, 3, 3, 4, 6, 9, 10]


出力結果から分かるように、left_i と len(left) が同じか、 もしくは right_i と len(right) が同じ時に、whileループを抜けています。

指摘させてもらった事は間違っていませんでした。

実は、この指摘をさせてもらった後に、このサンプルマージソート関数は、全ての whileループ判定の < を != に置き換えても問題ない気がしたので、全ての < を != を置き換えてみました。

以下が、その < を != 置き換えたプログラムの note 記事です。


後、これは重箱の隅をつつくような事なので報告しませんでしたが、p95 の、

次に、left_i は left の長さより短いので、

は、

次に、left_i は left の長さより小さいので、

の方が適切でしょう。left_i はインデックスを表す整数なので・・・


𝑷𝑺

2023-01-19 現在、この間違いは正誤表に載っていません。しかし、この間違いの確認をしていただける事が分かりました。

以下は、その確認が取れた清水川貴之さんのツイートです。


[追記]

対応していただきました。




#独学コンピューターサイエンティスト
#独CS #selftaughtcoder
#Python #Python3
#マージソート
#サンプルプログラム
#清水川貴之 さん