Pythonを使用したBottom Up MergeSort

Question

私はこれをやろうとして何時間も費やしました。誰かが私の間違いを指摘できますか？

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 

This visualizationが役に立ちます。なぜこれが起こっているのかまだ分かりません。

Answer 1

それは勇敢な努力だったが、あなたが作っ主な間違いはネストされたフロー制御アプローチしていました - 人間の心は非常に多くのネストされたwhile -loopsを扱うことができます。さらに、マージ関数が変更されるという事実は、aの位置にあります。は、何が起こっているのかを確認することを非常に困難にします。すべての行動を追跡できる素晴らしい心があるとしても、フロー制御ではなく問題に取り組むための脳のエネルギーを節約してください！

一般的には、プログラムをフラットに保つために、ネストされたフロー制御は避けてください。さらに、専用のオブジェクト指向プログラミングを行わない限り、aを変更する代わりに、特定の値を返そうとする必要があります。ここで

は、よりフラットと明示的なものを維持しようとマージする別のアプローチである：

def merge(merged, a, b): 

    if a and b: 
     return merge(merged + [min(a[0], b[0])], 
        a[1:] if min(a[0], b[0]) == a[0] else a, 
        b[1:] if min(a[0], b[0]) == b[0] and not a[0] == b[0] else b 
        ) 

    elif a and not b and len(a) > 1: 
     return merged + merge([], a[:len(a)/2], a[len(a)/2:]) 
    elif a and not b: 
     return merged + a 
    elif b and not a and len(b) > 1: 
     return merged + merge([], b[:len(b)/2], b[len(b)/2:]) 
    elif b and not a: 
     return merged + b 
    else: 
     return merged 

def mergesort(lst): 

    if not lst: 
     return [] 
    elif len(lst) == 2: 
     return [min(lst), max(lst)] 
    elif len(lst) == 1: 
     return lst 
    else: 
     return merge([], mergesort(lst[:len(lst)/2]), mergesort(lst[len(lst)/2:])) 

明示的なものを維持し、フロー制御構造を最小限に抑えるためにこの取り組みは、関数型プログラミングとして知られているプログラミングのスタイルで共通であります。

http://www.oreilly.com/programming/free/files/functional-programming-python.pdf

これはあなたが探しているが、私はそれが役に立てば幸い正確な答えではないかもしれません実現：あなたがここにアクセスすることができ、その上に素晴らしい無料の本があります。

Answer 2

私は疲れていますが、幸せです。私は、PythonTutor上の驚くべき視覚化ツールと繰り返しの数学に非常に注目して答えを見つけました。

プログラムは、長さ= 2の累乗の配列で問題なく動作します。 他のすべては、インデックス例外の配列を返します。 これらを処理するtry-exceptブロックを実装する必要があります。

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

私がこの問題にこれ以上の詳細を明らかにしていない理由は、snakes_on_a_keyboardがすでにはるかに優れた洗練されたソリューションを提供していたからです。