Re: [Haskell-cafe] k-minima in Haskell

Rereading this, I see in fact apfelmus explains this is "O(n + k*log n)" for the first k elements, which this discussion also maintains is the best case. So, there's no discrepancy. I think this is a very valuable post to read for the explanation. 2007/4/13, 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 :

...

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

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

(A stable quicksort, btw) "

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

2007/4/13, Thomas Hartman :

...

...

...

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 :

...

On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote:

...

On 4/11/07, Stefan O'Rear wrote:

...

If you want to be really explicit about it, here is a sort that will work:

sort [] = [] sort l@(x:_) = filter (x) l

(A stable quicksort, btw)

You may be missing a few recursive calls there :-)

Indeed.

Stefan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe