Three Beautiful Quicksorts

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

by edw519 • 18 years ago

29 14 18 years ago

jmount• 18 years ago

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/

pkrumins2• 18 years ago

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! :)

bayareaguy• 18 years ago

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

pkrumins2• 18 years ago

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

rkts• 18 years ago

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

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

kobs• 18 years ago

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

ola2• 18 years ago

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• 18 years ago

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]

martinflack• 18 years ago

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• 18 years ago

A more clear and equally useless code:

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

ardit33• 18 years ago

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• 18 years ago

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• 18 years ago

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

Three Beautiful Quicksorts

Related Stories