Erlang Bubble сортировать

Question

Я изучаю Erlang и решил внедрить в него пузырьковую сортировку, мне потребовалось некоторое усилие, и в результате я преуспел, но я вижу, что мое мышление неверно, есть ли более эффективный способ его реализации или нет?

bubble_sort(L) ->
if 
length(L) > 1 ->
    SL=bubble_sort_p(L),
    bubble_sort(lists:sublist(SL,1,length(SL)-1)) ++ [lists:last(SL)];
true -> L
end.

bubble_sort_p([]) -> [];    
bubble_sort_p([F | R]) ->
    case length(R) > 0 of
        true -> case F > hd(R) of
                true ->  [hd(R)] ++ bubble_sort_p([F|tl(R)]);
                false -> [F] ++ bubble_sort_p([hd(R)|tl(R)])
            end;
        false -> [F]
    end.

Answer 1

Реализация от макушки моей головы будет:

bubble_sort(L) -> bubble_sort(L, [], false).

bubble_sort([A, B | T], Acc, _) when A > B ->
  bubble_sort([A | T], [B | Acc], true);
bubble_sort([A, B | T], Acc, Tainted) ->
  bubble_sort([B | T], [A | Acc], Tainted);
bubble_sort([A | T], Acc, Tainted) ->
  bubble_sort(T, [A | Acc], Tainted);
bubble_sort([], Acc, true) ->
  bubble_sort(lists:reverse(Acc));
bubble_sort([], Acc, false) ->
  lists:reverse(Acc).

Если мы говорим об эффективности, мы, конечно, не должны идти на пузырьковую сортировку.

Answer 2

Есть ответ на http://en.literateprograms.org/Bubble_sort_%28Erlang%29

-module(bubblesort).
-export([sort/1]).
-import(lists, [reverse/1]).

sort(L) -> sort(L, [], true).
sort([], L, true) -> reverse(L);
sort([], L, false) -> sort(reverse(L), [], true);
sort([ X, Y | T ], L, _) when X > Y ->
sort([ X | T ], [ Y | L ], false);
sort([ X | T ], L, Halt) -> sort(T, [ X | L ], Halt).

Пример сортировки 2,4,3,5,1

сортировка ([2,4,3,5,1])

раунд 1

=> sort ([2,4,3,5,1], [], true)

=> sort ([4, 3,5,1], [2], true)

=> sort ([4,5,1], [3,2], false)

=> sort ([5,1], [4,3,2], false)

=> sort ([5], [1,4,3,2], false)

=>sort ([], [5,1,4,3,2], false)

=> sort ([2,3,4,1,5], [], true)

round 2

=> sort ([3,4,1,5], [2], true)

=> sort ([4,1,5], [3, 2], true)

=> sort ([4,5], [1,3,2], false)

=> sort ([5], [4,1, 3,2], false)

=> sort ([], [5,4,1,3,2], false)

=> sort ([2,3,1,4,5], [], true)

round 3

=> sort ([3,1,4,5], [2], true)

=> sort ([3,4,5], [1,2], false)

=> sort ([4,5], [3,1,2], false)

=> sort ([5], [4,3,1,2], false)

=> sort ([], [5,4,3,1,2], false)

=> сортировать ([2,1,3,4,5]true)

round 4

=> sort ([2,3,4,5], [1], false)

=> sort ([3,4,5], [2,1], false)

=> sort ([4,5], [3,2,1], false)

=> sort ([5], [4,3,2,1], false)

=> sort ([], [5,4,3,2,1], false)

=>sort ([1,2,3,4,5], [], true)

round 5

=> sort ([2,3,4,5], [1], верно)

=> сортировать ([3,4,5], [2,1], верно)

=> сортировать ([4,5], [3,2,1], true)

=> sort ([5], [4,3,2,1], true)

=> sort ([], [5,4,3, 2,1], верно)

=> [1,2,3,4,5]

Answer 3

И с использованием lists:foldr:

bubble(List) ->
    Step = fun
              (E,{S,[]}) -> {S,[E]};
              (E,{_,[X|XS]}) when E > X -> {swapped,[X|[E|XS]]};
              (E,{S,XS}) -> {S,[E|XS]}
           end,
    case lists:foldr(Step, {intact,[]}, List) of
        {intact,XS} -> XS;
        {swapped,XS} -> bubble(XS)
    end.

Answer 4

Позвольте мне переписать ваш код в гораздо более удобочитаемой форме (ничего не изменяя в семантике):

bubble_sort(L) when length(L) =< 1 ->
    L;
bubble_sort(L) ->
    SL = bubble_sort_p(L),
    bubble_sort(lists:sublist(SL,1,length(SL)-1)) ++ [lists:last(SL)].

bubble_sort_p([])  ->
    [];
bubble_sort_p([F]) ->
    [F];
bubble_sort_p([F,G|T]) when F > G ->
    [G|bubble_sort_p([F|T])];
bubble_sort_p([F,G|T]) ->
    [F|bubble_sort_p([G|T])].

Это должно значительно облегчить созерцание того, что происходит в программе.

Answer 5

Легко читать и понимать реализацию в восходящем направлении сортировки. Используемая хвостовая рекурсия, сложность вычислений и использование памяти являются классическими.

bsort([]) ->    [];
bsort([H|T]) ->         bsort([H|T],[]).

bsort([],[]) ->                 [];
bsort([],[H|T]) ->      [H|T];
bsort([A|B], Sorted) when is_list(Sorted) ->    M = lists:max([A|B]),   bsort([A|B] -- [M], [M] ++ Sorted).

Answer 6

-module(bubbleSort).
-compile(export_all).
-include_lib("eunit/include/eunit.hrl").

sort(L) ->
    sort(L, length(L), []).

sort(_L, 0, _Res) -> [];
sort([H | _T], 1, Res) -> [H | Res];
sort(L, Len, Res) ->
    T1 = lists:sublist(L, 1, Len),
    T2 = inner_sort(T1, []),
    Last = lists:last(T2),
   sort(T2, Len - 1, [Last | Res]).

inner_sort([A, B], Res) when (A < B)->
    Res ++ [A, B];
inner_sort([A, B], Res) ->
    Res ++ [B, A];
inner_sort([A, B | T], Res) when (A < B) ->
    inner_sort([B | T], Res ++ [A]);
inner_sort([A, B | T], Res) ->
    inner_sort([A | T], Res ++ [B]).

test()->
    L = [5, 3, -1, 10, 6, 100, 99],
    ?assert(sort([])  =:= []),
    ?assert(sort([1]) =:= [1]),
    ?assert(sort([1, 2, 3, 4]) =:= [1, 2, 3, 4]),
    ?assert(sort([10, 5, 3, 2, 1]) =:= [1, 2, 3, 5, 10]),
    ?assert(sort(L) =:= [-1, 3, 5, 6, 10, 99, 100]).