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

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

david nicol
June 29, 2004 15:10
Re: optimizing Short circuiting sort method based on [M]
Message ID:
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 Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About