-1

これはマージソート用の私の Python コードであり、23 行目でエラーが発生する理由がわかりませんIndexError。

23行目は、ループの前に置いてもエラーは発生しませんforが、forループ内ではlist index out of range. :(

from math import floor

def merge_sort(a,p,r):
 if p < r:
  q = (p+r)/2
  merge_sort(a,p,q)
  merge_sort(a,q+1,r)
  merge(a,p,q,r)

def merge(A,p,q,r):
 n1 = q - r +1
 n2 = r - q
 L = []
 R = []
 #print n1
 for i in range (1,n1):
  L.append(a[p+i-1])
 for j in range (1,n2):
  R.append(a[q+j])
 L.append(10000)
 R.append(10000)
 i,j=0,0

 for k in range (p,r):
  if L[i] <= R [j]: # This is where the error occurs
   A[k] = L[i]
   i = i + 1
  else :  
   A[k] = R[j]
   j = j + 1



a=[1,4,9,8,2,3,8,2,9]
merge_sort(a,1,len(a)) 
print a
4

2 に答える 2

0

これは Python ではなく、Python 構文を使用した Pascal です。

マージソートアルゴリズムの実装は次のとおりです ( Merge sort wiki articleに基づく):

def merge_sort(data):
    if len(data) <= 1:
        return data

    middle = len(data) / 2

    left = merge_sort(data[0:middle])
    right = merge_sort(data[middle:])

    return merge(left, right)


def merge(left, right):
    result = []

    while left or right:
        if left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
                continue

            result.append(right.pop(0))
            continue

        if left:
            result.append(left.pop(0))
        elif right:
            result.append(right.pop(0))

    return result


data = [1, 4, 9, 8, 2, 3, 8, 2, 9]
result = merge_sort(data)

assert len(data) == len(result)

print result
于 2012-08-25T09:52:50.647 に答える
0

私はコメント者/他のポスターに同意します。このスクリプトにはPython構文があります(通常の4つのスペースではないインデントを除いて...)が、Pythonicからはほど遠い...

とにかく、あなたの問題について: 問題がmergewhen に現れるよう(p,q,r)=(1,2,3)です。その場合、n1=0およびn2=1. ループしrange(1,n1)ても何も得られないため、L要素は 1 つしかありません (10000ループの外側に追加します)。

さて、for k in range (p,r)ループに到達したら:

  • 最初の反復でk=p=1、にL[0] <= R[0]足す1と=1ii
  • 2 回目の反復ではL[i]、 、つまりL[1]定義されていない にアクセスしようとします。したがって、IndexError.

いくつかのアドバイス:

  • デバッガーの使用方法を学びます。多くの IDE には何らかの実装が付属しており、非常に役立ちます。
  • リストはインデックス 0 から始まることに注意してください。これは、別の言語から来たときに忘れがちなことです。
于 2012-08-25T10:53:53.360 に答える