Re: Too Many Packages [was Re: Splitting locales...]
On Tue, Oct 10, 2000 at 11:45:26AM -0700, William Lee Irwin III wrote:
> On Tue, Oct 10, 2000 at 03:48:23PM +0200, Daniele Cruciani wrote:
> >> So, now I've a problem: cause I've surely missunderstood what the
> >> matter here and what is for radix sort, I've loose where's documented
> >> that alghoritms and how it can "sort" something in linear time (if it
> >> do sort at all).
>
> The general idea behind radix sort and bucket sort is address
> calculation. Radix sort specifically relies on trie-like mappings
> from the list/array elements to "buckets" where things with common
> digits are stored. The ingenious part is sorting from least to most
> significant digits. Bucket sort uses quantiles instead of digits.
> The important part of these sorting techniques is that the "buckets"
> in both radix sort and bucket sort are ordered.
>
thank, good, that give me an idea of what it is radix sort, but where
do i found a description, Knuth vol. 3 ? (unfortunally i've not that
here now).
> On Tue, Oct 10, 2000 at 03:58:58PM +0100, Jules Bean wrote:
> > The famous proof applies only to comparison sorts. Comparison sorts
> > are general, they work on any data which is totally ordered.
>
> The famous proof simply says that a comparison/exchange sort is
> equivalent to a binary decision tree, and as there are n! permutations
> of n letters, the decision tree must have n! nodes, and hence height
> lg n! and this is the lower time bound n lg n (note this is slightly
> pessimistic; lg n! = o(n lg n)).
>
> On Tue, Oct 10, 2000 at 03:48:23PM +0200, Daniele Cruciani wrote:
> >> I'm interested in parallel alghorithms so, if radix sort is such an
> >> alghoritms, I'll be happy to read about it. If it isn't and does some
> >> strange work over string, require more space and such I'll be happy to
> >> known it the same (curiosity).
>
> On Tue, Oct 10, 2000 at 03:58:58PM +0100, Jules Bean wrote:
> > I'm not aware of anjy parallel algorithm which is particularly clever.
>
> There is a fairly obvious parallel implementation of both radix and
> bucket sort.
> Bucket sort: sort the quantile buckets in parallel
> Radix sort: stuff buckets by the most significant digit for one pass
> sort those buckets in parallel
>
> Knuth notes that there were some MSD-first radix sorters out there during
> the dark ages; actually, the parallel radix sort as it's being described
> here is actually a bucket sort (beware of clashing terminology) with
> radix sort as the routine being used on the quantiles, and is covered
> by the first strategy.
>
> Cheers,
> Bill
> --
> "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
>
>
> --
> To UNSUBSCRIBE, email to debian-devel-request@lists.debian.org
> with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
--
Daniele Cruciani <cruciani@cli.di.unipi.it>
Universita` di Pisa - Informatica -
http://www.cli.di.unipi.it/~cruciani/
Reply to: