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

21–30 of 64 posts

Re: Quicksort is the new Hello World

#21

Post by jacquesm »

xentronium wrote: post #16
brazzy wrote: post #14

Earlier quoted context omitted.

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.

http://pastie.org/1367726 -- it's not that hard, really :) * especially with naive pivot from the middle of array

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  pivot do dec(j);
      if i  l then quicksort(a, l, j);
    if i
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]' 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 ?

Re: Quicksort is the new Hello World

#22

Post by dagw »

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…

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.

Re: Quicksort is the new Hello World

#24

Post by xentronium »

jacquesm wrote: post #21
xentronium wrote: post #16

Earlier quoted context omitted.

http://pastie.org/1367726 -- it's not that hard, really :) * especially with naive pivot from the middle of array

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 pivot do dec(j); if i l then quicksort(a, l, j); if i Do for loops in delphi/pascal iterate 'up to' or 'up to and including' ? If they iterate 'up to' then: It would seem to…

For loops are "Up to and including".

Arrays boundaries are [0..N] -> [0..1000] (1001 element actually, sorry if that confused you).

[add]: I could rewrite it in C, it should be trivial bijection, I believe.

Re: Quicksort is the new Hello World

#25

Post by quadhome »

xentronium wrote: post #16
brazzy wrote: post #14

Earlier quoted context omitted.

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.

http://pastie.org/1367726 -- it's not that hard, really :) * especially with naive pivot from the middle of array

Don't ever use that pivot code for more then 2^30 elements.

http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

Re: Quicksort is the new Hello World

#27

Post by noamsml »

I think I'm not alone when saying that the first thing I write in a new language I learn is some sort of project that requires a good understanding of the language's function-call model, of its object model, of a few specifics (strings, regices, data structures, arithmetic [depending on what I find interesting]), and that requires me to use some part of the standard library not readily available or to decompose my code into multiple files (or both). This helps me understand better what I'm doing, what I like about the language and what I don't. Examples of such projects include IRC bots, Lisp Interpreters, twitter clients, etc. (The one exception is Haskell, where I haven't gotten far enough to understand Monads well so I just wrote a completely functional RPN calculator).

Re: Quicksort is the new Hello World

#28

Post by jacquesm »

xentronium wrote: post #24
jacquesm wrote: post #21

Earlier quoted context omitted.

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 pivot do dec(j); if i l then quicksort(a, l, j); if i Do for loops in delphi/pascal iterate 'up to' or 'up to and including' ? If they iterate 'up to' then: It would seem to…

For loops are "Up to and including". Arrays boundaries are [0..N] -> [0..1000] (1001 element actually, sorry if that confused you). [add]: I could rewrite it in C, it should be trivial bijection, I believe.

I suspected as much, but indeed it confused the hell out of me, I've never written a line of pascal so my buffer overflow detector false triggered :)

Re: Quicksort is the new Hello World

#29

Post by srparish »

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…

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_Trans...

Re: Quicksort is the new Hello World

#30

Post by aristidb »

dagw wrote: post #22
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…

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.

Post reply on HN