1 
def merge (seq, p, q, r):
    # n1: length of sub-array [p..q]
    n1 = q - p + 1
    # n2: length of sub-array [q+1 ..r]
    n2 = r - q
    # Left and Right arrays
    left_arr = [] 
    right_arr = []
    for i in xrange(0, n1):
        left_arr.append( seq[p+i] )
    for j in xrange(0, n2):
        right_arr.append( seq[q+j+1] )

    j=0
    i=0
    for k in xrange(p,r+1):
        if left_arr[i]<= right_arr[j]:
            seq[k]=left_arr[i]
            i+=1
        else:
            seq[k]=right_arr[j]
            j+=1
    return seq

s = [2,4,5,7,1,2,3,6]
p = 0
q = 3
r = 7
print merge(s,p,q,r)

使い方：

  1. ソートされていないシーケンス s が、シーケンスをマージする必要があるインデックス番号とともに取得されます。(p=初期、r=最終、q=中間)

  2. ここで、left_arr と right_arr はそれぞれ [p,q]、[q+1, r] です。

  3. left_arr と right_arr の初期値 (i=0、j=0) を取ります。シーケンス seq を反復処理します...

  4. 繰り返しながら、seqの値をソートされた値に置き換えています...

上記の関数は、最後の番号「7」までソートできます..最後に、「IndexError」を示します。例外処理を使用してそれをキャッチして修正できますが、マージソートの場合は多すぎると思います.コードをできるだけ簡単に修正するのを手伝ってくれませんか。

私はアルゴリズムを学んでいます.. (次の本: Thomas H. Cormen によるアルゴリズムの紹介)

4

3 に答える 3

1

コードの問題は、 をループしているということです。xrange(p, r+1)そのため、繰り返しのループ中にiorの値がorjの値と等しくなり、最終的に が発生する可能性があります。len(left)len(right)IndexError

def merge(seq,p,q,r):
    left=seq[p:q+1]       #a better way to fetch the list
    right=seq[q+1:]       
    i=0
    j=0
    #you shuldn't loop over the length of seq as that might make the value of either i or j
    # greater than the length of left or right lists respectively.
    # so you should only loop until one of the lists is fully exhausted

    while i<len(left) and j<len(right):
        if left[i] <= right[j] :
            seq[i+j]=left[i]
            i+=1
        else:
            seq[i+j]=right[j]
            j+=1

    #now the while loop is over so either right or left is fully traversed, which can be
    #find out my matching the value of j and i with lenghts of right and left lists respectively

    if j == len(right):
        seq[i+j:]=left[i:]  #if right is fully traversed then paste the remaining left list into seq
    elif i==len(left):      #this is just vice-versa of the above step
        seq[i+j:]=right[j:] 
    print seq

s = [2,4,5,7,1,2,3,6]
p = 0
q = 3
r = 7
merge(s,p,q,r)

出力：

[1, 2, 2, 3, 4, 5, 6, 7]
于 2012-09-28T15:11:23.833 に答える
1

問題は、最後の反復で i が 4 になり、存在しない left_arr[5] にアクセスしようとしていることです。i または j が対応する配列のサイズよりも大きくなったときに停止条件を追加してから、他の配列の残りのすべての要素を seq に追加する必要があります。

動作するコードは次のとおりです。

def merge (seq, p, q, r):
    # n1: length of sub-array [p..q]
    n1 = q - p + 1
    # n2: length of sub-array [q+1 ..r]
    n2 = r - q
    # Left and Right arrays
    left_arr = seq[p:n1] #here 
    right_arr = seq[n1:r+1]  #here
    j=0
    i=0
    for k in xrange(p, r+1):
        if left_arr[i]<= right_arr[j]:
            seq[k]=left_arr[i]
            i+=1
            if i > n1-1: #here
                break
        else:
            seq[k]=right_arr[j] #here
            j+=1
            if j > n2-1:
                break
    if i >= len(left_arr): #from here down
        seq[k+1:] = right_arr[j:]
    elif j >= len(right_arr):
        seq[k+1:] = left_arr[i:]

    return seq

s = [2,4,5,7,1,1,1,1]
p = 0
q = 3
r = 7
print merge(s,p,q,r)

コードを編集した場所をコメントでマークしました。

于 2012-09-28T14:38:21.517 に答える
0

left_arrとの反復中に配列インデックスをチェックしませんでしたright_arr。別の配列が終了したら、いずれかの配列の左側をマージする必要があります。

for k in xrange(p,r+1):
    if left_arr[i]<= right_arr[j]:
        seq[k]=left_arr[i]
        i+=1
    else:
        seq[k]=right_arr[j]
        j+=1

    # --------------- add this ----------------
    # if any array ends, merge the left elements of the other array
    if i >= len(left_arr):
        seq[k:] = right_arr[j:]
        break
    elif j >= len(right_arr):
        seq[k:] = left_arr[i:]
        break
    # --------------- end ----------------
return seq
于 2012-09-28T14:49:33.917 に答える