Christopher Smith wrote:
On Jun 27, 2007, at 12:15 PM, Stewart Stremler wrote:
Unexpected truncation?
Huh?
Stewart is not used to such short code and probably assumed that there
must be more. Nope, that's it. You can plug that into hugs or similar
haskell system and start sorting.
Plus, it needs comments.
I disagree here. You need to know the language to interpret it, but even
Yeah, this is a tiny snippet of code. It implements quicksort. Everyone
knows how quicksort works. Not the sort of thing that needs comments.
Also, as it seems to be a standard implementation of quicksort, it's
going to have _lousy_ worst-case performance.
Sure. I don't believe this was meant to be an example of "best sort
EVAR!". Simply how easy it is to write.
Exactly. Written as a teaching tool not for actual high performance use.
How easy is it to add such things?
Again, one can reasonably extrapolate from the code sample just how
difficult this is.
Oh, and it's broken -- the pivot is *always* the lowest element in the
array, which means it's a pretty sad (and slow) quicksort.
Yep, the pivot is always the first element in the list. Not necessarily
the best way to start. It's just an example.
Better to look at Arrays.sort, which is part of Java, and generally
implemented with a good quicksort...and as this is what's used in the
Indeed, I wasn't aware of that. I just searched google for java
quicksort and found something with source I could conveniently link to.
Seriously, you're missing the point of the post.
Indeed and wouldn't be the first time someone on this list has missed
the point. :)
How about an exploded description of the syntax. I see most of it,
except that I don't see how the pivot is selected, which is really
the key to quicksort.
The quicksort function I pasted takes one argument which is a list so
that matches the (p:xs) but and the p is given the value of the first
element (the car of the list to use Lisp nomenclature) and the xs
becomes the rest (the cdr of the list). So now you can do comparisons
using the p and recurse on the xs part which is like cdr'ing down a list
in lisp.
Here is some more info on quicksort in haskell:
http://en.literateprograms.org/Quicksort_(Haskell)
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
