[erlang-questions] Bubble sort in Erlang

[Joe Armstrong]

I would do this is steps

Whats the problem?

To start with here's the *wrong* code

    bs([A,B|T]) when A =< B -> [A|bs([B|T)];
    bs([A,B|T]) -> [B|bs([A|T])];    %% SWAP
    bs([A]) -> [A];
    bs([]) -> [].

The problem is that in the line marked "SWAP" we need to somehow
record the fact that we have performed a swap so we can "do it again"

We modify the first program adding a flag to record if we need to "do it again"
and an accumulator (the third argument) to collect the result.

Like this:

bs([A,B|T], Flag, L) when A =< B ->  bs([B|T], Flag, [A|L]);
bs([A,B|T], _, L)                          ->  bs([A|T], true, [B|L]);
bs([X], Flag, L)                            ->  bs([], Flag, [X|L]);
bs([], Flag, L)                              ->  {Flag, reverse(L)}.

The flag is changed to true if the arguments in the list are out of
order, otherwise
it is just passed unchnaged through the function calls.

When the initial list is finished we return the flag and the reversed
accumulator

Now we need an iterator, this is easy.

bs(L) ->
    case bs(L, false, []) of
	{true, L1}  -> bs(L1);  %% if the flag is true - do it again
	{false, L1} -> L1
    end.

You could actually get rid of the reverse in bs/3 by noting which
order the list is
in - on the first pass you bubble out of order elements to the right,
on the second to
the left etc. (ie on the first pass you try to make a list with the
smallest element
first, on the second pass with the largest element last (since the
list is reversed
at the end of the first pass)).

The library routines for sort use this technique, they also special case sorting
short lists.

/Joe



On 5/19/07, Milen Dzhumerov <gamehack@REDACTED> wrote:
> 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.
>
> Kind regards,
> Milen
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>