Bubblesort in Erlang

It’s amazing how if a language isn’t a part of your daily work, how rusty you get at it. Oh erlang, how I didn’t mean to neglect you! I finally convinced Ian to give Erlang a shot, and he’s been going through Joe Armstrong’s book. He decided to write bubblesort, and it took him hours. This is what he had to say:

I’m having some difficulty
getting used to the idea of a language where every variable is a const.
its interesting, though.

but I have to admit the one line erlang quicksort is one of the
prettiest code snippits I’ve ever seen.

but “=:=” for equivalence? a three character long operator? who do
they think they are?

I wrote bubble sort and merge sort in erlang last night. it took
hours. the code looks horrible. for the first time since learning
basic in high school I feel like a foreigner in a strange land. its
invigorating.

actually I find it a bit intimidating. when something takes more than a
few lines of code I wonder if I’m doing it wrong. if joe armstrong ever
saw my bubble sort he’d probably take my book away.

I decided to give it a shot. It’s certainly a far better exercise than FizzBuzz. Given that I had written a neural network in erlang before, I figured I’d be more than ok with bubblesort. Right?

Wrong.

It’s taken an embarrassingly long time to get it right, plus, I took a shortcut that isn’t very optimal. If I ever had to write this in an interview in Erlang, They’d take my keyboard away. Here’s what I came up with:

-module(bubblesort).
-export([sort/1]).

sort([First | Rest]) ->
sort_helper([First | Rest], swap(First, Rest)).

sort_helper(List, New_list) when List =:= New_list ->
List;
sort_helper(List, [First | Rest]) ->
sort_helper([First | Rest], swap(First, Rest)).

swap(Current, []) ->
[Current];
swap(Current, [First | Rest]) when Current =
[Current] ++ swap(First, Rest);
swap(Current, [First | Rest]) ->
[First] ++ swap(Current, Rest).


Notice that I use the guard “List =:= New_list” to determine if a swap took place. In a large list, this would add n comparisons on every pass. Horrible. But since it’s an exercise, I neglected to keep track of swaps.

More than half the time was wrestling with the syntax. I had forgotten a lot of it, and mixed up [First, Rest] with [First | Rest], and I kept forgetting that I needed to prefix the functions by their module names. It’s bubblesort:swap(…) when you want to call it, and I was scratching my head for 10 mins. But the other time was just thinking recursively. Unless you’re working in a language the heavily uses recursive to iteration, you don’t often use it. But defn I prefer recursive as it’s much more succinct. Can anyone come up with a one-liner Bubblesort?

For reference, “the one liner” quicksort Ian was talking about:

qsort([]) -> 
[];
qsort([Pivot | T]) ->
qsort([X || X <- T, X < Pivot]) ++ [Pivot] ++ qsort([X || X = Pivot]).

Advertisements

4 thoughts on “Bubblesort in Erlang

  1. Alright, you captured by Friday lunch time attention. 😉 After whipping out a few uglier versions, I finally came up with this:-module(bubble).-export([sort/1]).sort(List) -> case lists:foldl(fun(A, {_, []}) -> {noswap, [A]}; (A, {_, [B|R]}) when A < B -> {swap, [B,A|R]}; (A, {S, R}) -> {S, [A|R]} end, {noswap, []}, List) of {swap, New} -> sort(lists:reverse(New)); {noswap, _} -> List end.(Blech – what’s the best way to post code in a Blogger comment?)Get back into Erlang! It’s good for you! 😉

  2. <>for the first time since learningbasic in high school I feel like a foreigner in a strange land. itsinvigorating.<>I totally agree with Ian.Your blog entry prompted me to blog on the topic of coding style in Erlang: http://curious-attempt-bunny.blogspot.com/2007/10/coding-style-in-erlang.htmlOne thing to note:sort([First | Rest]) -> sort_helper([First | Rest], swap(First, Rest)).This involves Erlang rebuilding the list. In the case you don’t need First and Rest but you can do this:sort([First | Rest] = List) -> sort_helper(List, swap(List)).

  3. sort(X) -> sort(X, s(X)). sort(X,X) -> X; sort(_,Y) -> sort(Y, s(Y)). s([X,Y|L]) when X>=Y -> [X|s([Y|L])]; s([X,Y|L]) when X< -> [Y|s([X|L])]; s(L) -> L.

  4. took me an few hours to implement while i was studying 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.

    I think I start to like Erlang but I need to start thinking differently

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s