Three Beautiful Quicksorts

[edw519]

http://www.catonmat.net/blog/three-beautiful-quicksorts/

[pkrumins]

Yay! My article made to the front page of Hacker News again :)

I just wanted to tell you that if you like my articles, you can subscribe to my rss feed here:

http://feeds.feedburner.com/catonmat

Thanks! :)

[jmount]

It is beautiful code, but a lot more attention needs to be paid to the production quality version. In particular most beautiful quicksorts take O(n^2) time on a list filled with identical items (see Tim Peters ch. in the Python Cookbook or my article: http://www.win-vector.com/blog/2008/04/sorting-in-anger/

[bayareaguy]

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 [] = []

[ola → bayareaguy]

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)

[fallintothis → ola]

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]

[ola → fallintothis]

Serves me right, should have tested the code before I submitted it. Just s/span/partition/ and it should work.

[kobs → bayareaguy]

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

[martinflack → bayareaguy]

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) ])))))

[d0mine → bayareaguy]

A more clear and equally useless code:

  qsort [] = []
  qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

[pkrumins → bayareaguy]

Wow. That's so beautiful and elegant! Thanks for sharing! I added it to my article!

[rkts → pkrumins]

It's also too inefficient to belong anywhere in the vicinity of working code.

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

[ardit33]

ummm.. recursive solution? What will happen if you try to sort a million of items. Don't you run out of stack space at some point.

I know that some compilers are smart, and can inline things, but still method calls are not necessary the most efficient way to go.

Sure, it might look pretty, but it is not efficient.

[fp → ardit33]

At 1,000,000 items you have 20 (in the best case, at least) levels of recursion. I can assure you, your stack space is more than sufficient for that.

Also, you only have to push a handful of pointers to the stack, which doesn't seem to be expensive to me.

[schtog]

Python:

  def quicksort(lst):
      if len(lst) == 0:
          return []
      else:
          return quicksort([x for x in lst[1:] if x <   lst[0]]) + [lst[0]] + \
                 quicksort([x for x in lst[1:] if x >=   lst[0]])