Front page | perl.perl5.porters |
Postings from June 2004
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