Re:Three Beautiful Quicksorts
by jmount on Thursday July 10, 2008 @09:05PM
(#243108)
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/
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:
Re:Three Beautiful Quicksorts
by schtog on Friday July 11, 2008 @10:23PM
(#244232)
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]])
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! :)
Beautiful, elegant, useless. Maybe that should be the Haskell motto.
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.
Also, you only have to push a handful of pointers to the stack, which doesn't seem to be expensive to me.