Re: [Fwd: Re: [FWP] sorting text in human-order]
> "JSD" == Jonathan Scott Duff <[EMAIL PROTECTED]> writes: JSD> On Mon, Jan 01, 2001 at 04:31:42PM -0600, Jarkko Hietaniemi wrote: >> (1) Quicksort has a weak point where it goes deep into the Quadratic Land: >> (nearly) already ordered data. No, that is not so far-fetched a case. >> Mergesort has no similar weakpoints: its performance is in fact >> consistently N log N. >> >> (2) Mergesort is stable. Quicksort is not. JSD> I figured it was something like this, but wanted to know if there JSD> were any other reasons. JSD> I recently tracked down a bug in some software that we've been using for JSD> years that turned out to be an implicit assumption that perl's sort JSD> would be stable when, of course, it's not. Had perl 5.7 come along JSD> sooner I might never have caught the bug or been bitten by it :-) there was a thread the other day in c.l.p.misc about this very issue. regardless of the stableness of perl's internal sort, you should never assume stability unless it is specified. perl5 never specified this and relying on 5.7 for it is foolish IMO. adding sort stability is not hard even with an unstable sort algorithm. on this note, i then propose that we do specify perl6's sort to be stable. we can at this point do that and by keeping our sort algorthm choices to stable ones, we can deliver it. i would never sepc perl5's sort as stable due to all the older versions out there with unstable quicksorts. uri -- Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books The Best Search Engine on the Net -- http://www.northernlight.com
Re: [FWP] sorting text in human-order
Marc Lehmann wrote: > > On Sat, Dec 30, 2000 at 05:31:29AM +, "David L. Nicol" <[EMAIL PROTECTED]> >wrote: > > I do not know exactly what the perl5 default sort heuristic is, aside that > > it tries to DWIM both numeric and string data. > > There is no heuristic, the default is simply $a cmp $b, so I am not sure > what you mean with DWIM ;) I was wrong. If it did a crowley/schwartz transform, it would DWIM. That is what I am proposing: that perl6 _sort_ do, by default, an implied crawley/schwartz transform. | -- David Nicol 816.235.1187 [EMAIL PROTECTED] Today in art class, draw your sword
Re: [Fwd: Re: [FWP] sorting text in human-order]
Jarkko Hietaniemi wrote:
> "sort heuristic"? "DWIM both numeric and string data"? There is
> no "heuristic". There is no "DWIM". Perl's sort() does by default
> string sort based on the byte values of the strings of its argument
> list. That's it. Period. Full stop.
Oh.
$ perl -le 'foreach (sort (0..199)){print}' | head
Once again I am a misguided fool.
Thank you for your patience.
--
David Nicol 816.235.1187 [EMAIL PROTECTED]
Re: [Fwd: Re: [FWP] sorting text in human-order]
On Mon, Jan 01, 2001 at 04:31:42PM -0600, Jarkko Hietaniemi wrote: > (1) Quicksort has a weak point where it goes deep into the Quadratic Land: > (nearly) already ordered data. No, that is not so far-fetched a case. > Mergesort has no similar weakpoints: its performance is in fact > consistently N log N. > > (2) Mergesort is stable. Quicksort is not. I figured it was something like this, but wanted to know if there were any other reasons. I recently tracked down a bug in some software that we've been using for years that turned out to be an implicit assumption that perl's sort would be stable when, of course, it's not. Had perl 5.7 come along sooner I might never have caught the bug or been bitten by it :-) thanks again, -Scott -- Jonathan Scott Duff [EMAIL PROTECTED]
