0

次のエラーが表示されます。

Traceback (most recent call last):
  File "Lab1.py", line 24, in <module>
    b = mergesort(a)
  File "Lab1.py", line 19, in mergesort
    left = mergesort(lst[:middle])
  File "Lab1.py", line 21, in mergesort
    return merge(left, right)
  File "Lab1.py", line 12, in merge
    result.append(right[j])
IndexError: list index out of range

...このコードで：

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            j += 1
    result.append(right[j])
    return result

def mergesort(lst):
    if len(lst) <= 1:
        return lst
    middle = int(len(lst) / 2)
    left = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    return merge(left, right)

a = [3,1,2,5,9,6,7]
b = mergesort(a)
print('Input #1: ' + ', '.join(str(x) for x in a))
print('Output #1: ' + ', '.join(str(x) for x in b))

Python 3.3.2を使用しています。

4

1 に答える 1

2

while ループに追加1します。最終的に、それが有効なインデックスではない場合j。リストへのインデックスは範囲内に収まる必要があります(含まれている、除外されている)。j = len(right) - 1j = len(right)[0, length)0length

ループ内で をインクリメントする前に追加jし、結果を残り (既にソート済み) で拡張します。

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

IndexErrorスライスが;を発生させることはありません。インデックスが利用可能な値の範囲外の場合、空のリストが返されます。left[i:]との少なくとも 1 つがright[j:]空のリストになります。

デモ：

>>> a = [3,1,2,5,9,6,7]
>>> b = mergesort(a)
>>> print('Input #1: ' + ', '.join(str(x) for x in a))
Input #1: 3, 1, 2, 5, 9, 6, 7
>>> print('Output #1: ' + ', '.join(str(x) for x in b))
Output #1: 1, 2, 3, 5, 6, 7, 9
于 2013-09-06T09:22:14.427 に答える