[erlang-questions] Bubble sort in Erlang

[andrew cooke]

wasn't sure my previous post was clear.  i don't know if you're prefer to
work things out yourself, but below (after your email) i have written a
sketch of what i would expect things to turn out like once you add an
accumulator list.  code is not tested.

> Hi all,
>
> I've recently picked up the "Programming Erlang" book and started
> experimenting with Erlang. So I wanted to implement some toy
> algorithms - would you believe me that I was kind of stuck for
> several days on the train while going to work implementing a simple
> bubble sort algorithm? I think FP really hit my head - that's the
> first time I've tried any functional programming. The hardest part
> for me was (and still is) maintaining and mutating the state (like
> whether a swap has occurred). So I thought because I have to use
> recursion instead of iteration, I could maintain the state using
> parameter passing. Here it goes, my first Erlang toy program:
>
> -module(bsort).
> -export([bubble_sort/1, bstage/1, bstage/2]).
>
> bubble_sort([A,B|Tail]) when Tail =/= [] ->
> 	{Status, List} = bstage([A,B|Tail]),
> 	case Status of
> 		sorted -> List;
> 		not_sorted -> bubble_sort(List)
> 	end;
> bubble_sort([A,B]) ->
> 	if
> 		A > B -> [B, A];
> 		true -> [A, B]
> 	end;
> bubble_sort([A]) -> [A];
> bubble_sort([]) -> [].
>
> bstage(L) ->
> 	{Swapped, List} = bstage(L, false),
> 	case Swapped of
> 		false -> {sorted, List};
> 		true -> {not_sorted, List}
> 	end.
>
> bstage([A,B|Tail], Swapped) when Tail =/= [] ->
> 	if
> 		A > B -> {_, List1} = bstage([A|Tail], true),
> 				{true, [B] ++ List1};
> 		true -> {Swap, List} = bstage([B|Tail], Swapped),
> 				{Swap, [A] ++ List}
> 	end;
> bstage([A,B], Swapped) ->
> 	if
> 		A > B -> {true, [B,A]};
> 		true -> {Swapped, [A,B]}
> 	end.
>
> Any comments are greatly appreciated.


this is the kind of thing i would expect - i haven't tested the code

sort(List) ->
  repeat_til_done(List, []).

repeat_til_done([], Acc) ->
  lists:reverse(Acc);
repeat_til_done([A], Acc) ->
  repeat_til_done([], [A|Acc]);
repeat_til_done([A,B|Tail], Acc) when A > B ->
  repeat_til_done([B|Tail], [A|Acc]);
repeat_til_done([A,B|Tail], Acc) ->
  sort(lists:reverse(Acc) ++ [B,A|Tail]).

i don't know if the logic is correct, but the idea is that when you have a
swap (the last condition) you just restart.

andrew

>
> Kind regards,
> Milen
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
>