Re: Too Many Packages [was Re: Splitting locales...]
William Lee Irwin III wrote:
>> Those lower bounds on sorting are incorrect. Bucket sorting and
>> radix sorting can reduce the sorting time to O(n), given appropriate a
>> priori information about the sorting keys (either a bounded space for
>> radix sort, or a rough distribution for an unbounded space; the bound
>> on bucket sorting is actually the expected sorting time).
On Fri, Oct 06, 2000 at 04:00:46AM -0700, Joey Hess wrote:
> Yes, and the sphagetti sort is O(1) (with a O(n) setup though ;-).
> Some sorts arn't particularly practical though.
This is a ridiculous attempt to discredit sorting methods which
are, as far as I know, noncontroversial and well established. It's
difficult to deny the practicality of a sort (radix sort) that was
invented, used, and used widely and in large-scale punch card sorting
efforts well prior to the invention of computers and even the year 1900.
According to Knuth, there were even "electric sorting machines" as early
as the 20's. It wasn't very difficult with gears and clockwork, and you
can do it even more easily with a program.
Both Knuth and Rivest (with Cormen and Leiserson) describe radix sort
in gory detail. Bucket sorting with the quantiles and so on is just a
variation of radix sorting according to Knuth, and some algorithms book
by Standish that I have sitting around gives an example of bucket sort
mapping airport codes to floating-point numbers (but calls it "proxmap
sort"). Baase discusses both bucket and radix sorting as well.
Having written and benchmarked code that actually performed these
sorts for sophomore class assignments, I noticed a few things.
(1) They weren't particularly difficult to write.
(2) They were much faster than the n lg n sorts.
(3) There was no fancy setup involved (the code was even short).
For your benefit I'll enumerate the URL's of information about these
books from amazon.com (though I hope you'll go elsewhere for the actual
purchase). I don't like Standish, but I'll list it anyway.
Cheers,
Bill
--
Baase: http://www.amazon.com/exec/obidos/ASIN/0201612445/qid=971107981/sr=1-2/102-4192738-9348928
Knuth: http://www.amazon.com/exec/obidos/ASIN/0201896850/qid=971108031/sr=1-4/102-4192738-9348928
Rivest et al: http://www.amazon.com/exec/obidos/ASIN/0262031418/qid=971108080/sr=1-1/102-4192738-9348928
Standish: http://www.amazon.com/exec/obidos/ASIN/0201591189/qid%3D971108157/102-4192738-9348928
--
"The good Christian should beware of mathematicians and all those who
make empty prophecies. The danger already exists that mathematicians
have made a covenant with the devil to darken the spirit and confine man
in the bonds of Hell."
-- St. Augustine
Reply to: