> You may be missing a few recursive calls there :-)
Indeed.
I'm confused.
Is this a legitimate stable quicksort, or not? (My guess is, it is
indeed legit as written.)
This was also the first I have heard of stability as a sort property.
http://perldoc.perl.org/sort.html may shed some light on this...
"A stable sort means that for records that compare equal, the original
input ordering is preserved. Mergesort is stable, quicksort is not. "
Is this description a fair characterization of stability for the
current discussion?
I'm a bit confused but if I understand correctly sort from the prelude
is non stable quicksort, which has O(k n^2) as the worst case, whereas
stable quicksort has O( k* log n + n).
non-stable quicksort is just sort from the prelude:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
If any in the above was incorrect, please holler.
2007/4/12, Stefan O'Rear <[EMAIL PROTECTED]>:
On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote:
> On 4/11/07, Stefan O'Rear <[EMAIL PROTECTED]> wrote:
> >
> >If you want to be really explicit about it, here is a sort that will
> >work:
> >
> >sort [] = []
> >sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l
> >
> >(A stable quicksort, btw)
>
> You may be missing a few recursive calls there :-)
Indeed.
Stefan
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
