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
