MergeSort und Quicksort in Erlang funktioniert nicht

Question

Kann mir jemand helfen herauszufinden, was mit meinen Sortieralgorithmen nicht stimmt. Ich bekomme keine Fehler, bleibe aber in einer Art Endlosschleife stecken. Die Funktionen scheinen individuell zu funktionieren.

msort([])-> 
    []; 
msort(L)-> 
    {L3, L4} = msplit(L, [],[]), 
    merge(msort(L3), msort(L4)). 

msplit([], L1, L2)-> 
    {L1, L2}; 
msplit([H|[]], L1, L2)-> 
    msplit([], [H]++L1, L2); 
msplit([H|[H2|T]], A, B)-> 
    msplit(T, A++[H], B++[H2]). 

merge(L, [])->L; 
merge([], R)->R; 
merge([H1|T1], [H2|T2])-> 
    if H1 < H2 
     -> [H1|merge(T1, [H2|T2])]; 
     true-> [H2|merge([H1|T1], T2)] 
    end. 

qsort([])->[]; 
qsort([H|T])-> 
    {A, B} =qsplit(T, H, [], []), 
    Small =qsort(A), 
    Large = qsort(B), 
    lists:append(Small,Large). 

qsplit([], H, A, B)-> 
    {A++[H], B}; 
qsplit([H|T], P, A, B)-> 
    if H > P-> 
      qsplit(T, P, A++[H], B); 
     true-> qsplit(T, P, A, B++[H]) 
    end. 

Nach einigen Änderungen der Code ordnungsgemäß funktioniert:

msort([]) -> 
     []; 
msort([_] = L) -> 
    L; 
msort(L)-> 
    {L3, L4} = msplit(L, [],[]), 
    merge(msort(L3), msort(L4)). 

msplit([], L1, L2)-> 
    {L1, L2}; 
msplit([H|[]], L1, L2)-> 
    msplit([], [H|L1], L2); 
msplit([H|[H2|T]], A, B)-> 
    msplit(T, [H|A], [H2|B]). 

merge(L, [])->L; 
merge([], R)->R; 
merge([H1|T1], [H2|T2])-> 
    if H1 < H2 
     -> [H1|merge(T1, [H2|T2])]; 
     true-> [H2|merge([H1|T1], T2)] 
    end. 

qsort([])->[]; 
qsort([_] = L)->L; 
qsort([H|T])-> 
    {A, B} =qsplit(T, H, [], []), 
    Large =qsort(A), 
    Small = qsort(B), 
    lists:append(Small,[H|Large]). 

qsplit([], _, A, B)-> 
    {A, B}; 
qsplit([H|T], P, A, B)-> 
    if H > P-> 
      qsplit(T, P, [H|A], B); 
     true-> qsplit(T, P, A, [H|B]) 
    end. 

Answer 1

Wenn Sie msort/1 mit einer Liste rufen Sie nur ein Element enthält [X] Ihre msplit/1 wird {[X], []} zurück, wo Sie msort/1 mit einem Punkt nennen [X] und so auf. Sie können das Problem beheben, indem das Hinzufügen msort/1 Funktion Klausel:

msort([])-> 
    []; 
msort([_] = L) -> 
    L; 
msort(L)-> 
... 

Ein ähnliches Problem ist in Ihrem qsort/1.

Es gibt mehr Probleme in Ihrem Code. Sie sollten alle Ihre A++[H] durch [H] ++ A ersetzen, die noch besser als [H|A] geschrieben wird. Es hat großen Einfluss auf die Effizienz Ihres Codes. Sie können [H, H2 | T] anstelle von [H | [H2 | T]] verwenden, es ist schön syntaktischer Zucker, der Lesbarkeit hilft.