develooper Front page | perl.perl5.porters | Postings from June 2004

Re: optimizing Short circuiting sort method based on [M]

From:
david nicol
Date:
June 29, 2004 15:10
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
1088547007.2310.42.camel@plaza.davidnicol.com
On Fri, 2004-06-25 at 10:55, Glenn Linderman wrote:

> One trivial way to take advantage of the hint is to recall that the 
> lowly N-squared bubble sort (and variations) produces one high (or low) 
> value per pass, and that for small M and large N, that M*N is smaller 
> than N lg N.

With regard to yesterday's post in which I'm thinking aloud,

Considering bubbling or inserting the new, smaller element, based
on expected average-case number of comparisons required, I think that
bubbling will be better for M less than or equal to five.

The reason is, binary search _always_ has to do lg(M-1) comparisons
while bubbling can do anywhere from one to M-1 comparisons because
bubbling stops when the new element has done like a mature executive and
risen to the point where it can't rise any further, an expected number
of (M-1)/2 comparisons.

(M-1)/2 is equal to lg2(M-1) at M=5.








-- 
david nicol
    "People used to be able to read my thoughts, but
it doesn't appear to work any more. Should I eat less cheese?"
                                               -- Elizabeth Woods




nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About