4 ms·
My vote for the most beautiful quicksort is this Haskell one: module Quicksort where quicksort (x:xs) = quicksort [ i | i <- xs, i < x ] ++
by bayareaguy 18y 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 [] = []
- 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)