0

楽しみのために、k=3の場合にkwayマージソートを実装しようとしています。再帰的にmergesortを呼び出すのに問題はありませんが、3つのリストを一緒にマージしようとしていますが、ソートされたリストを取得できません。基本的な考え方は、すべてのリストの最初の要素を比較し、それが最小の場合はリストに追加することです。すべてのアレイに対してこのプロセスを繰り返します。

def three_merge(a,b,c):
    i =0
    j =0
    k=0
    list = []
    while(i < len(a) or j < len(b) or k < len(c)):
        while(a[i] <= b[j] and a[i] <= c[k]):
            list.append(a[i])
            i=i+1
            print i
        while(b[j] <= a[i] and b[j] <= c[k]):
            list.append(b[j])
            j=j+1
            print j
        while(c[k] <= a[i] and c[k] <= b[j]):
            list.append(c[k])
            k=k+1
            print k
   return list    

a = [1,2]
b = [-5,10]
c = [-11, 100]
print three_merge(a,b,c)
4

3 に答える 3

1

問題は、並べ替えられたリストに追加する各値のインデックスを進めることです。i, j, kつまり、インデックスは、リストからすべての要素を取得した後、対応する入力リストの長さよりも 1 大きくなります。したがって、さまざまな入力リストの要素の値を比較すると、最終的には実行しようとしているポイントに到達し、実際にはa[len(a)]、while は常にインデックス エラーを返します。

于 2013-02-08T09:22:08.650 に答える
1

n-way マージの簡単な関数を次に示します。ご不明な点がございましたら、お気軽にお問い合わせください。

def merge(*args):
    lst = list(args)
    idx = [0] * len(lst)
    out = []

    while lst:
        m = 0
        for i in range(len(lst)):
            if lst[i][idx[i]] < lst[m][idx[m]]:
                m = i
        out.append(lst[m][idx[m]])
        idx[m] += 1
        if idx[m] >= len(lst[m]):
            del lst[m]
            del idx[m]

    return out


print merge([1,2,11], [2,9], [8]) # [1, 2, 2, 8, 9, 11]
于 2013-02-08T11:05:30.257 に答える
0

3 つのリストのマージを、2 つのリストの 2 つのマージの合成と考えてみませんか?

def merge(a,b):
    L = a
    l = b
    i = 0
    j = 0
    res = []
    if (len(b)>len(a)):
        L=b
        l=a
    #print L
    #print l
    while (i<len(L)):
        if(len(l)>0):
            while (j<len(l)):
                if (L[i]<=l[j]):
                    res.append(L[i])
                    del L[i]
                    break
                else:
                    res.append(l[j])
                    del l[j]
        else:
            #print res
            res = list(res+L)
            L=[]
            break
    if len(l)>0:
        res = list(res+l)
        l=[]
    return res

def threeMerge(a,b,c):
    return merge(merge(a,b),c)

aa = [1,2]
bb = [-5,3,20]
cc= [-11, 23,45]
print threeMerge(aa,bb,cc)
于 2013-02-08T09:35:42.680 に答える