0

次のマージソートコードを書きました：

def merge_sort(self,a):

    #console.log(len(a))
    if len(a) <= 1:
        return a
    left = []
    right = []
    result = []
    middle = int(len(a)/2)
    print middle

    left = a[:middle] #set left equal to the first half of a
    right = a[middle:] #set right equal to the second half of a
    print left
    print right

    left = self.merge_sort(left)
    right = self.merge_sort(right)
    result = self.merge(left, right)

    return result

そして、コードをマージします:

def merge(self, left, right):
    result = []
    while len(left) > 0 or len(right) > 0:

        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left.pop(1)    #remove the first element from left

        elif len(left) > 0:
            result.append(left[0])
            left = left.pop(1)    #remove the first element from left

        elif len(right) > 0:
            result.append(right[0])
            right = right.pop(1)  #remove the first element from right

        else:
            result.append(right[0])
            right = right.pop(1)
    return result

配列を送ります: a = [12,0,232]

そして、次の出力（異なる反復）を取得し、最後の出力でエラーが発生します。エラーが発生する理由が正確に理解できないのを助けてくださいありがとう！

(1 [12] [0, 232]) (1 [0] [232])

トレースバック (最新の呼び出しは最後): ...\Sort_Class.py"、116 行目、マージ中 left = left.pop(1) #左から最初の要素を削除 IndexError: 範囲外のインデックスをポップ

4

2 に答える 2

3

コードに問題があります。たとえば、この選択ではすべて存在します:

result.append(left[0])
left = left.pop(1)

これは次のようになります。

result.append(left.pop(0))

問題は次のとおりです。

  1. Python リストは 0 ベースのインデックスを使用するためleft[0]、リストの最初の要素はそうではなくleft[1]、left.pop(0)最初の要素をleft.pop(1)ポップし、2 番目の要素をポップします
  2. left.pop(1)リストを変更するため、リストではなくポップされた要素を返します。left = left.pop(1)ここではあまり意味がありません。
  3. left[0]最初の要素を取得してからポップする必要はありませんleft.pop(0)
于 2012-10-15T01:17:32.237 に答える
0

私は.pop()あなたが思っていることをしないと思います。たとえば、次の行です。

left = left.pop(1)    #remove the first element from left

から「最初の」(つまりゼロ番目の) 要素を削除しませんleft。 .pop(1)は 2 番目の要素です。

>>> a = [10,20,30,40]
>>> a.pop(1)
20
>>> a
[10, 30, 40]

さらに、 を設定するa = a.pop(1)と、aはリストではなく数値になります。

>>> a = [10,20,30,40]
>>> a = a.pop(1)
>>> a
20

どちらも機能しません。投稿されたばかりの回答に記載されているように、これらをdel left[0]またleft = left[1:]は単に置き換えることができます。result.append(left.pop(0)):^) ただし、別の問題を明らかにする修正: ここのロジックが原因で、コードが無限ループに陥る:

    if len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:

の場合left[0] > right[0]、分岐は行われず、leftまたはrightのいずれにも何も起こらず、トラップされます。これを微調整して、この場合の右分岐動作を追加すると、コードが機能するように見えます。

>>> import random
>>> def check():
...     for length in range(1, 10):
...         for trial in range(10000):
...             v = [random.randrange(-10, 10) for i in range(length)]
...             assert merge_sort(v) == sorted(v)
...     return True
... 
>>> check()
True
于 2012-10-15T01:20:36.920 に答える