Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!emory!att!pacbell.com!ames!uhccux!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: Lying
Message-ID: <4298@goanna.cs.rmit.oz.au>
Date: 16 Nov 90 08:10:10 GMT
References: <6097@lanl.gov>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 39

In article <6097@lanl.gov>, jlg@lanl.gov (Jim Giles) writes:
>G> (Actually, you might speed the _test_ up by sorting the addresses of all
>G> potentially aliased objects and then moving through the sorted list and
>G> comparing adjacent items.  This is still _at_least_ N*log(N).

 X> Great, now you don't even know how to sort a collection of numbers in
 X> linear time.

In all fairness, the quote from X here explicitly says "numbers",
G having said "addresses", and we may reasonably take it that this
means hardware addresses and hardware numbers.  (I understood X's
claim not to have omitted the qualification "in the number of bytes"
to refer to generic sorts that didn't know they had numbers to
work with.  Evidently I misunderstood.)

There is a new book
	Introduction to Algorithms
	Thomas H. Cormen, Charles E. Leiserson, & Ronald L. Rivest
	MIT Press, 1990
	ISBN 0-262-03141-8	(MIT Press, world-wide)
	ISBN 0-07-013143-0	(McGraw-Hill, USA)
I like it a lot.  Section 9.4 says on p180
	Bucket sort runs in linear time on the average.  ...
	bucket sort assumes that that the input is generated by
	a random process that distributes elements uniformly
	over the interval [0,1).
They explicitly use the formula O(n), where n is the number of keys.

Clearly addresses aren't random floating-point numbers, but
	(ptr - ptrmin)/scale
where double scale = ptrmax - ptrmin;
_is_ in the interval [0,1) and might be close enough to random.

This is not a defence of X.  I'm just pointing out to anyone who
might have missed it that there _is_ a method described in the
literature as sorting numbers in time linear in the number of keys.
-- 
The problem about real life is that moving one's knight to QB3
may always be replied to with a lob across the net.  --Alasdair Macintyre.