Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort is the new Hello World

blog.rmontanaro.com

Post reply on HN
Print view View original

41–50 of 64 posts

Re: Quicksort is the new Hello World

#41

Post by sizzla »

DanielBMarkham wrote: post #38

Yet another article that completely misses the point. The point of "Hello World" is to show a noob how to fire up the editor, compile, and see something happen. And btw, here's the answer in F#: let rec qsort = function | [] -> [] | x::xs -> let smaller,larger = List.partition (fun y -> y

This looks like yet another Haskell "variant." From what I can tell this sort does not occur in place and thus would not make a particularly good quicksort. Memory use, number of accesses per element, etc. This style of programming is more suitable for heapsort or maybe mergesort.

Re: Quicksort is the new Hello World

#42

Post by sizzla »

pmjordan wrote: post #13
l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

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…

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.

Re: Quicksort is the new Hello World

#43

Post by sizzla »

aristidb wrote: post #30
dagw wrote: post #22

Earlier quoted context omitted.

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 s…

This is the real "sort" used by GHC 7: 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.

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

or this (also taken from rosetta code)?

  #include 
  #include  // for std::partition
  #include  // for std::less
  
  template
  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
 void quicksort(RandomAccessIterator first, RandomAccessIterator last)
  {
    quicksort(first, last, std::less::value_type>());
  }
The above code is more verbose?

Re: Quicksort is the new Hello World

#44

Post by hristov »

l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

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
Does this work?

Re: Quicksort is the new Hello World

#45

Post by zbanks »

sizzla wrote: post #41
DanielBMarkham wrote: post #38

Yet another article that completely misses the point. The point of "Hello World" is to show a noob how to fire up the editor, compile, and see something happen. And btw, here's the answer in F#: let rec qsort = function | [] -> [] | x::xs -> let smaller,larger = List.partition (fun y -> y

This looks like yet another Haskell "variant." From what I can tell this sort does not occur in place and thus would not make a particularly good quicksort. Memory use, number of accesses per element, etc. This style of programming is more suitable for heapsort or maybe mergesort.

You can't exactly sort "in place" in functional languages like F#/Haskell... at least trivially.

Re: Quicksort is the new Hello World

#46

Post by sizzla »

Deestan wrote: post #15
sb wrote: post #10

tl; dr, but a quick note: the presented algorithm takes the first element as the pivot element p: qsort (p:xs) = ... This is not recommended as it results in worst-case behavior on sorted input lists. (Another commentor correctly pointed out that it requires extra memory for the intermediate lists, too.)

It is just a toy implementation. If we're going to worry about practicals, then it's not recommended to use your own general purpose sorting implementations at all . For general purpose sorting, the standard library "always" has the best implementation.

Any knowledge about your data set, how much of it varies, etc can vastly improve your performance over any canned standard library solution. Sorting ints? Radix-sort that mofo.

Re: Quicksort is the new Hello World

#47

Post by sizzla »

_tef wrote: post #35

It is like fizzbuzz/binary search in that most people think they can write it and they get it wrong. Quicksort requires careful selection of pivots, and is unstable. (Many scripting languages (perl, python) are opting for stable sorts) Check out Bentley&McIllroy's Engineering Quick Sort for a guide about the problems implementing a production ready quicksort. If you're going to teach them something easy, simple and r…

I would rather teach them:

1) how to write a program that guesses a number you thought of by doing binary search.

2) solve 2-queens

3) solve n-queens

4) solve knapsacking or some other combinatorial problem requiring memoization or DP. Of course, I wouldn't tell them any of those buzzwords that are meant to scare them away from just hacking on it.

Their mind will be blown regardless of the language they used and they'll get a feel for O() without even opening Cormen.

Re: Quicksort is the new Hello World

#49

Post by neilc »

sizzla wrote: post #42
pmjordan wrote: post #13

Earlier quoted context omitted.

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…

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). Som…

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

Re: Quicksort is the new Hello World

#50

Post by sizzla »

LostInTheWoods2 wrote: post #34

I usually implement a tic-tac-toe game as my first project when learning a new language. Tic-tac-toe, properly implemented, will give you a pretty good tour of a language. But with that said, Hello world, still serves it purpose.

This is a great example of making something that is challenging for a novice, yet not so challenging they give up. The reward is much higher than watching some numbers show up in the correct order and you tend to cover more of the language (2D array or your own abstraction of such, I/O, control flow, etc.).
Post reply on HN