0

Jeff Erickson による 3 ページのメモに記載されているマージ ソート アルゴリズムを実装しようとしています。しかし、アルゴリズムは正しく、実装も正しいように見えますが、入力リストを変更せずに出力として取得しています。誰かが異常を指摘できますか?

def merge(appnd_lst, m):
    result = []
    n = len(appnd_lst)
    i, j = 0, m
    for k in range(0, n):
        if j < n:
            result.append(appnd_lst[i])
            i += 1
        elif i > m:
            result.append(appnd_lst[j])
            j += 1
        elif appnd_lst[i] < appnd_lst[j]:
            result.append(appnd_lst[i])
            i += 1
        else:
            result.append(appnd_lst[j])
            j += 1

    return result


def mergesort(lst):
    n = len(lst)
    if n > 1:
        m = int(n / 2)
        left = mergesort(lst[:m])
        right = mergesort(lst[m:])

        appnd_lst = left
        appnd_lst.extend(right)
        return merge(appnd_lst, m)
    else:
        return lst


if __name__ == "__main__":
    print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])
4

1 に答える 1

3

マージ関数には 3 つのエラーがあり、いくつかのインデックス エラーと間違った比較演算子の使用があります。Python リストのインデックスは 0 .. len(list)-1 から始まることを思い出してください。

* ...
6        if j > n-1:  # operator wrong and off by 1
* ...
9        elif i > m-1: # off by 1
* ...
于 2013-09-15T02:06:22.763 に答える