3 ms·
Three Beautiful Quicksorts
- jmount 18y agoIt 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/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/
- pkrumins 18y agoYay! 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 http://feeds.feedburner.com/catonmat Thanks! :)
- bayareaguy 18y agoMy 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 [] = []
- pkrumins 18y agoWow. That's so beautiful and elegant! Thanks for sharing! I added it to my article!
- rkts 18y agoIt's also too inefficient to belong anywhere in the vicinity of working code. Beautiful, elegant, useless. Maybe that should be the Haskell motto.
- kobs 18y agoNearly 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 http://en.literateprograms.org/Category:Quicksort
- ola 18y agoYou'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 18y agoYou'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 18y agoServes me right, should have tested the code before I submitted it. Just s/span/partition/ and it should work.
- deleted 18y ago[deleted]
- martinflack 18y agoIn this paper they show how to do something like this in CL. http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispComp.pdf 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 18y agoA more clear and equally useless code: qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
- ardit33 18y agoummm.. 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 18y agoAt 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 18y agoPython: 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]])