1

再帰マージソートアルゴリズムにこの擬似コードを実装しようとしていました:

**procedure**  *mergesort*(L = a1, a2,…,an )
**if**  n  > 1 **then** 
     m := ⌊n/2⌋
     L1 := a1, a2,…,am 
     L2 := am+1, am+2,…,an
     L   := merge(mergesort(L1), mergesort(L2 ))
{L is now sorted into elements in increasing order}

**procedure**  *merge*(L1, L2 :sorted lists)
L := empty list
**while** L1  and L2  are both nonempty
 remove smaller of first elements of L1 and L2 from its list; 
         put at the right end of L
 **if** this removal makes one list empty 
     **then** remove all elements from the other list and append them to L
return L {L is the merged list with the elements in increasing order}

これまでのところ、すべてをコーディングしましたが、正しく実行されず、実行するたびに次のように出力されます: function merge at 0x0000000002024730. Pythonコードは次のとおりです。

#Recursive Merge Sort
import math
ent = [10000, 967, 87, 91, 117, 819, 403, 597, 1201, 12090]
def merge(L1, L2):

        while len(L1) and len(L2) != 0:
            L.append(L1[0])
            L1.remove(L1[0])
            L.append(L2[0])
            L2.remove(L2[0])
            if len(L1) == 0:
                L.append(L2)
            elif len(L2) == 0:
                L.append(L1)
        return L


def mergesort(ent):

if len(ent)>1:
    m=math.floor(len(ent)/2)
    L1 = []
    L2 = []
    L1=L1+ent[:m]
    L2=L2+ent[m+1:len(ent)]
    L=merge(mergesort(L1),mergesort(L2))




print(merge)

関数が再帰的に一緒に動作することが想定されている方法について疑問があります。そのため、正しく解決してコーディングすることはできないと思います。ヘルプや提案はありますか?

4

1 に答える 1

4

あなたは実行していませんが、関数自体mergeを印刷しています。これを行う：

print(merge())

ただし、ロジックが少し混乱しているため、再帰関数さえありません。

この質問を見てください

また、必要なのはmergesortを呼び出すことだと思います：

def mergesort(ent):
    if len(ent)>1:
        m=math.floor(len(ent)/2)
        L1 = ent[:m]
        L2 = ent[m+1:len(ent)]
        L=merge(mergesort(L1),mergesort(L2))
return L

そしてそれを実行します：

print(mergesort(ent))
于 2013-11-15T03:33:58.577 に答える