[Haskell-cafe] k-minima in Haskell

[Thomas Hartman]

And for reference, here is again stefan's "stable" quicksort from his
earlier post.

"
sort [] = []
sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l

(A stable quicksort, btw)
"

This is the code whose legitimacy I am requesting confirmation of.

2007/4/13, Thomas Hartman <tphyahoo at gmail.com>:
> > > 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 <stefanor at cox.net>:
> > On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote:
> > > On 4/11/07, Stefan O'Rear <stefanor at cox.net> 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
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>