[Haskell-cafe] k-minima in Haskell

[Thomas Hartman]

Trying to understand this better I also came across

http://groups.google.de/group/fa.haskell/browse_thread/thread/1345c49faff85926/8f675bd2aeaa02ba?lnk=st&q=%22I+assume+that+you+want+to+find+the+k%27th+smallest+element%22&rnum=1&hl=en#8f675bd2aeaa02ba

where apfulmus gives an implementation of mergesort, which he claims

"runs in O(n) time instead of the expected O(n log n)"

Does that mean you can have the k minima in O(n) time, where n is
length of list, which would seem to be an improvement?

  mergesort []  = []
  mergesort xs  = foldtree1 merge $ map return xs

  foldtree1 f [x] = x
  foldtree1 f xs  = foldtree1 f $ pairs xs
     where
     pairs []        = []
     pairs [x]       = [x]
     pairs (x:x':xs) = f x x' : pairs xs

  merge []     ys     = ys
  merge xs     []     = xs
  merge (x:xs) (y:ys) =
      if x <= y then x:merge xs (y:ys) else y:merge (x:xs) ys


2007/4/13, Thomas Hartman <tphyahoo at gmail.com>:
> 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
> > >
> >
>