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 <[EMAIL PROTECTED]>:
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 <[EMAIL PROTECTED]>:
> > > 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
