5 ms·
I wouldn't call recursion boring. Quicksort in Haskell is probably my favorite two lines of code: quicksort [] = [] quicksort (x:rest) = quicksort [y | y <
by anindyabd 11y ago
I wouldn't call recursion boring. Quicksort in Haskell is probably my favorite two lines of code:
quicksort [] = []
quicksort (x:rest) = quicksort [y | y <- rest, y <= x] ++ [x] ++ quicksort [y | y <- rest, y > x]
- nemesisrobot 11y agoIt's been discussed before, but that's not really quicksort though (since it's not in-place)[0] 0: http://stackoverflow.com/q/7717691/1235548 http://stackoverflow.com/q/7717691/1235548
- emmelaich 11y agoDo we know that for sure? I mean - could a sufficiently smart compiler actually create machine code which _did_ do it in-place?
- jmount 11y agoThis variant (with the <= comparison) takes c N^2 on lists of length N that a repeated constant ( http://www.win-vector.com/blog/2008/04/sorting-in-anger/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/ ).