7 ms·

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter (< p) x

• pmjordan 16y ago
  In fairness, in-place sorting usually isn't what you want in functional programming. Immutable data structures help enforce the pure functional constraints. Of course, in practice, your library code will probably make a mutable copy, sort that in-place and then return an immutable copy/representation of the result, which is hopefully more efficient. (Disclaimer: I'm no Haskell programmer; my FP experience is limited to Lisp dialects) EDIT: As a curious example, Clojure's sort function actually converts the sequence to a (Java) Array and calls java.util.Arrays.sort() on it, then turns it back into a sequence: https://github.com/clojure/clojure/blob/b578c69d7480f621841ebcafdfa98e33fcb765f6/src/clj/clojure/core.clj#L2329 https://github.com/clojure/clojure/blob/b578c69d7480f621841e...
  • sizzla 16y ago
    Advancing compilers is hard. When people argue efficiency as a compiler implementation detail that is going to get worked out, they forget about many who have fallen before them. You can argue some older languages were written in a way in which it was (reasonably) easy to write a compiler that generates code with little performance overhead when compared to assembly (at worst a factor of 2 to 4, back in the 80s). Some popular languages keep adding abstractions and constructs that the compiler can actually deal with without some new compiler research breakthrough.
    • neilc 16y ago
      When people argue efficiency as a compiler implementation detail that is going to get worked out, they forget about many who have fallen before them. Yes; see also http://prog21.dadgum.com/40.html http://prog21.dadgum.com/40.html
      • sizzla 16y ago
        Thanks. Beatifully written and I love the print-shop analogy. It's nice he is into the C&C Portland Wiki, there's golden nuggets of wisdom everywhere. I am reposting the link from his blog. http://c2.com/cgi/wiki?SufficientlySmartCompiler http://c2.com/cgi/wiki?SufficientlySmartCompiler Personally of the higher-level languages, I found SBCL to be crazy good at optimizing, of course given a few nudges with a compiler directive or two. By inspecting the dissasembly, I could validate it was doing the "right-thing" (TM), but then again, I do the same to check the C/C++ compiled code.
• brazzy 16y ago
  Indeed. It's amazing just how difficult it is to write a correct in-place quicksort that handles all edge cases. It won't be short and elegant either. Just go ahead and try it.
  • xentronium 16y ago
    http://pastie.org/1367726 http://pastie.org/1367726 -- it's not that hard, really :) * especially with naive pivot from the middle of array
    • jacquesm 16y ago
      Your code: program qsortTest; const N = 1000; var a: array [0..N] of integer; i: integer; procedure quicksort(var a: array of integer; l, r: integer); var i, j, temp: integer; pivot: integer; begin pivot := a[(l+r) div 2]; i := l; j := r; while i < j do begin while a[i] < pivot do inc(i); while a[j] > pivot do dec(j); if i <= j then begin temp := a[i]; a[i] := a[j]; a[j] := temp; inc(i); dec(j); end; end; if j > l then quicksort(a, l, j); if i < r then quicksort(a, i, r); end; begin { populating the array } for i := 0 to N do a[i] := random(N); writeln('initial array'); for i := 0 to N do write(a[i]:6); writeln; quicksort(a, 0, N); writeln; writeln('sorted array'); for i := 0 to N do write(a[i]:6); writeln; end. Do for loops in delphi/pascal iterate 'up to' or 'up to and including' ? If they iterate 'up to' then: It would seem to me that on the initial call to 'quicksort' the '1000' gets passed in to 'r', the value of 'r' then gets passed in to 'j'. Now if "'a[j]' < p" will refer to the uninitialized value in a[1000] and compare it to p, the first decrement will not take place, i<=j and now the code will swap with a[i] with a[1000]. This should cause the uninitialized value (0?) to end up as the first element in the sorted output array. I hope I analyzed that correct, I don't have access to a pascal/delphi compiler here. When you run your code do you see the output starting with a '0' element ? Is there another element from the input array missing in the output ? If pascal/delphi loops iterate up-to-and-including did you actually intend to sort an array of 1001 elements ?
      • 16y ago
• lelele 16y ago
  > Thus, even if the sample code is simple and elegant, a real-world implementation would surely be a bit longer than the given example. Nice thought. What's the purpose of showing code which you won't be using in a real-world application? Making you think the language is more expressive than what it really is? Many people say Haskell code is elegant and concise. Would this be the case if code we were shown would be real-world Haskell?
• dagw 16y ago
  I find this a recurring problem when trying to learn Haskell. On the one hand you have lots of books and tutorials talking about how simple and elegant Haskell is. Showing all the awesome things you can do with two lines of code. Then I try to write simple and elegant Haskell like that and find it runs an order of magnitude slower than my Python code. I wish more Haskell proponents would spent less time showing off simple and elegant code, and more time showing fast and correct code.
  • aristidb 16y ago
    This is the real "sort" used by GHC 7: http://hackage.haskell.org/packages/archive/base/4.3.0.0/doc/html/src/Data-List.html#sort http://hackage.haskell.org/packages/archive/base/4.3.0.0/doc... It's pretty elegant, too, if less than the inefficient pseudo-qsort shown by the OP.
    • sizzla 16y ago
      Correct me if I am wrong but they are actually using mergesort (mergeAll) as it is significantly faster in Haskell than in-place quicksort (qsort). That means there is a lot of overhead for doing something simple like an in-place qsort that should be much faster than a mergesort. I am at a loss on why the provided code is any more elegant than: http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29 http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29 or this (also taken from rosetta code)? #include <iterator> #include <algorithm> // for std::partition #include <functional> // for std::less template<typename RandomAccessIterator, typename Order> void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order) { if (last - first > 1) { RandomAccessIterator split = std::partition(first+1, last, std::bind2nd(order, *first)); std::iter_swap(first, split-1); quicksort(first, split-1, order); quicksort(split, last, order); } } template<typename RandomAccessIterator> void quicksort(RandomAccessIterator first, RandomAccessIterator last) { quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>()); } The above code is more verbose?
      • merijnv 16y ago
• srparish 16y ago
  Not only is it making two-passes for filtering, it also has to do another pass to append "lesser" onto [p] and "greater". And that is for a single recursion so these multiple passes are happening per-recursive call. Here's a page with some actual haskell quicksorts: http://www.haskell.org/haskellwiki/Introduction/Direct_Translation http://www.haskell.org/haskellwiki/Introduction/Direct_Trans...
• amalcon 16y ago
  It would be pretty difficult to write an in-place sort in Haskell, given that it only has mutable state through monads (and I doubt anyone wants to go into a monad just to sort something). GHC is pretty good at optimizing list concatenations, so that's probably not a big deal either. You're absolutely right about the two-pass filter, though.
  • sizzla 16y ago
    It's not that good, which is why they gave up on using quicksort in Data.List .
• hristov 16y ago
  Ok, I am still learning Haskell, but I thought I would try to fix the above so that there is only one filter pass: qsort :: Ord a => [a] -> [a] qsort [] = [] qsort [x] = [x] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where (lesser, greater) = foldl split ([],[]) xs where split (left, right) x = if x<p then (left:x, right), else (left, right:x) Does this work?
  • deleted 16y ago
    [deleted]
  • deleted 16y ago
    [deleted]
  • l0stman 16y ago
    I had to look up what the `:' operator does and it adds an element to the beginning of the list. So the last line should be split (left, right) x = if x<p then (x:left, right), else (left, x:right)