CODEWITHSUNDEEP
erlang
mr. D
mr. D

Reputation: 58

MergeSort and Quicksort in Erlang not working

Can someone help me figure out what's wrong with my sorting algorithms. I get no errors but get stuck in some kind of infinite loop. The functions seem to work individually.

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.

After some changes the code is working properly:

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.

Upvotes: 2

Views: 362

Answers (1)

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

If you call msort/1 with a list containing just one item [X] your msplit/1 will return {[X], []} where you call msort/1 with one item [X] and so on. You can fix it by adding msort/1 function clause:

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

A similar problem is in your qsort/1.

There are more problems in your code. You should replace all your A++[H] with [H] ++ A which is even better written as [H|A]. It has big impact to an efficiency of your code. You can use [H, H2 | T] instead of [H | [H2 | T]], it is nice syntactic sugar which helps readability.

Upvotes: 1

Related Questions