Learning Erlang: The Beautiful Quicksort

Posted by Giovanni Intini | Filed under Erlang, Learning Erlang, Programming

Sometimes you really have to stop and contemplate how beautiful code is. This is an erlang quicksort algorithm, one of the most efficient (if I remember correctly it’s the most efficient) sorting algorithms. I still remember the pains of implementing it in C.

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

Short + Clean + Elegant = Beautiful.

Permalink | Comments (8) | Apr 3, 2007

8 Responses to “Learning Erlang: The Beautiful Quicksort”

  1. tom Says:
    April 3rd, 2007 at 5:32 pm

    blanket statements are usually wrong :)

    ‘the most efficient’ in certain circumstances ;)

  2. Giovanni Intini Says:
    April 3rd, 2007 at 5:49 pm

    Then I almost remembered correctly :D

    Do you remember what’s the least efficient order for quicksort? The reverse ordered array?

  3. fullo Says:
    April 3rd, 2007 at 7:55 pm

    as I said saturday erLang seems to me very similar to prolog :)

    partition([], _, [], []).
    partition([X|Xs], Pivot, Smalls, Bigs) :-
    ( X @
    Smalls = [X|Rest],
    partition(Xs, Pivot, Rest, Bigs)
    ; Bigs = [X|Rest],
    partition(Xs, Pivot, Smalls, Rest)
    ).

    quicksort([]) —> [].
    quicksort([X|Xs])—>
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller),
    [X],
    quicksort(Bigger).

    via wikipedia

  4. Giovanni Intini Says:
    April 3rd, 2007 at 8:36 pm

    It’s 14 against 5. That’s no prolog if you ask me :)

  5. riffraff Says:
    April 4th, 2007 at 12:18 am

    I agree it is prolog-like, it’s just that prolog lacks list comprehensions :)

    Yet, I think the prolog version could be shortened, if you consider that partition or an equivalent could be builtin it becomes two-liner (or five if you split on commas)

  6. Giovanni Intini Says:
    April 4th, 2007 at 1:57 am

    Omg, I’m among a group of prolog advocates :)

  7. thor Says:
    June 6th, 2007 at 9:56 am

    One thing should be noted: C version of quicksort sorts array _in_place_. So, yes, Erlang and Haskell versions of quicksort will look cleaner and simpler, but complexity of C code has its roots – efficiency.

  8. Giovanni Intini Says:
    June 6th, 2007 at 1:34 pm

    It’s obvious C is more efficient, but most of the times you can give up some cycles for simpler and quicker programming.

    CPU Time costs much less than programmers’ time.