News for hackers. Stuff that matters.
Re:Three Beautiful Quicksorts by bayareaguy on Thursday July 10, 2008 @10:50PM (#243177)
My vote for the most beautiful quicksort is this Haskell one:

  module Quicksort where

  quicksort (x:xs) = 
      quicksort [ i | i <- xs, i < x ] 
      ++ [x] ++
      quicksort [ i | i <- xs, i >= x ]

  quicksort [] = []
Re:Three Beautiful Quicksorts by ola on Friday July 11, 2008 @12:11AM (#243238)
You're doing two filters with list comprehensions which you could switch with one span:

    quicksort (x:xs) = let (a, b) = span (< x) xs in (quicksort a) ++ [x] ++ (quicksort b)
Re:Three Beautiful Quicksorts by fallintothis on Friday July 11, 2008 @06:13AM (#243394)
You're doing two filters with list comprehensions which you could switch with one span:

    quicksort (x:xs) = let (a, b) = span (< x) xs in (quicksort a) ++ [x] ++ (quicksort b)
Actually, this is incorrect. span will split the list as soon as it finds the predicate to be false on an item, instead of finding the smaller elements of the whole list. So, for instance, if we try your function as in the following, we get improper results:

  > quicksort [1, 2, 3, 2, 1]
  [1,2,1,2,3]
  > quicksort [1, 2, 3, -2, -1]
  [1,2,-2,-1,3]
  > quicksort [1, 2, 3, -2, 0, -1]
  [1,2,-2,-1,0,3]
Re:Three Beautiful Quicksorts by ola on Friday July 11, 2008 @08:06AM (#243441)
Serves me right, should have tested the code before I submitted it. Just s/span/partition/ and it should work.
Re:Three Beautiful Quicksorts by kobs on Thursday July 10, 2008 @11:18PM (#243196)
Nearly identical implementation in Erlang:

  qsort([]) -> [];

  qsort([Pivot|Rest]) ->
    qsort([ X || X <- Rest, X < Pivot]) 
    ++ [Pivot] ++ 
    qsort([ X || X <- Rest, X >= Pivot]).
More: http://en.literateprograms.org/Category:Quicksort
Re:Three Beautiful Quicksorts by martinflack on Friday July 11, 2008 @02:22AM (#243311)
In this paper they show how to do something like this in CL. http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispCo...

  (defun qsort (ax)
    (and ax
         (let ((a (car ax))
               (x (cdr ax)))
           (append (qsort [y (y <- x) (< y a)])
                   (list a)
                   (qsort [y (y <- x) (>= y a)])))))
If you want the x:xs stuff you could load fare-matcher and write something like:

  (defun qsort (l)
    (ematch l
      (nil nil)
      ((cons x xs) (append (qsort [ i (i <- xs) (< i x) ])
                           (list x)
                           (qsort [ i (i <- xs) (>= i x) ])))))
Re:Three Beautiful Quicksorts by d0mine on Friday July 11, 2008 @07:22AM (#243419)
A more clear and equally useless code:

  qsort [] = []
  qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Re:Three Beautiful Quicksorts by pkrumins on Thursday July 10, 2008 @10:59PM (#243183)
Wow. That's so beautiful and elegant! Thanks for sharing! I added it to my article!
Re:Three Beautiful Quicksorts by rkts on Thursday July 10, 2008 @11:55PM (#243223)
It's also too inefficient to belong anywhere in the vicinity of working code.

Beautiful, elegant, useless. Maybe that should be the Haskell motto.