2

私はこれを行うために数え切れないほどの時間を費やしてきました。誰かが私の間違いを指摘できますか？

aは単なるリストでtmpあり、サイズの空のリストですlen(a)

z基本的にlen(a)

a = [6,5,4,3,2,1] print 'unsorted:',a z = len(a) tmp = range(len(a))

これが私のソート機能です：

def sort(a,tmp):
        width=1
        while(width<z):
                p=0
                while(p<z):
                        left =p
                        middle = p+width
                        right = p+2*width
                        merge(a,left,middle,right,tmp)
                        p = p+2*width
                t=0        
                while(t<z):
                    a[t]=tmp[t]
                    t=t+1
                width=width*2
                print '\n'

ここにマージ機能があります：

def merge(a,iLeft,iMiddle,iRight,tmp):
        i = iLeft
        j = iMiddle
        k = iLeft
        print iLeft,iMiddle,iRight,'[',i,j,k,']'
        #print i ,j, k,'\n\n'

        while(i<iMiddle or j<iRight):
                if(i<iMiddle and j<iRight):
                        if(a[i]<a[j]):
                                tmp[k]=a[i]
                                i += 1
                                k += 1
                        else:
                                tmp[k]=a[j]
                                j += 1
                                k += 1

                elif (i==iMiddle):
                        tmp[k] = a[j]
                        j += 1
                        k += 1
                elif (j==iRight):
                        tmp[k]= a[i]
                        i += 1
                        k += 1

[このビジュアライゼーション] が役立つかもしれません。なぜこのような動きをするのか、いまだにわかりません。

どこが間違っているのかわかりませんか？それはインデントですか、それともループですか？

Output ::
unsorted: [6, 5, 4, 3, 2, 1]
0 1 2 [ 0 1 0 ]
2 3 4 [ 2 3 2 ]
4 5 6 [ 4 5 4 ]


0 2 4 [ 0 2 0 ]
4 6 8 [ 4 6 4 ]
Traceback (most recent call last):
  File "BUmer.py", line 45, in <module>
    sort(a,tmp)
  File "BUmer.py", line 14, in sort
    merge(a,left,middle,right,tmp)
  File "BUmer.py", line 27, in merge
    if(a[i]<a[j]):
IndexError: list index out of range

この視覚化が役立つ場合があります。なぜこれが起こっているのかはまだわかりません。

4

2 に答える 2

1

疲れたけど幸せな気分。PythonTutor の驚くべき視覚化ツールと、反復の数学への非常に熱心な注意によって、答えに出くわしました。

プログラムは、長さ = 2 の累乗である配列に対して正常に動作します。それ以外のすべての配列では、インデックス外の例外が発生します。これらを処理するには、try-except ブロックを実装する必要がありました。

とにかく、今私は知っています。関数型プログラミングのガイダンスについては、snakes_on_a_keyboard に感謝します。

この問題の詳細を明らかにしない理由は、snakes_on_a_keyboard が既にはるかに優れたエレガントなソリューションを提供しているためです。

于 2016-05-22T08:46:56.443 に答える