*To*: debian-devel@lists.debian.org*Cc*: William Lee Irwin III <wli@holomorphy.com>*Subject*: Re: Too Many Packages [was Re: Splitting locales...]*From*: Daniele Cruciani <cruciani@cli.di.unipi.it>*Date*: Tue, 10 Oct 2000 22:45:40 +0200*Message-id*: <20001010224540.A946@colossus.cli.di.unipi.it>*Mail-followup-to*: debian-devel@lists.debian.org, William Lee Irwin III <wli@holomorphy.com>*In-reply-to*: <20001010114526.A13135@holomorphy.com>; from wli@holomorphy.com on Tue, Oct 10, 2000 at 11:45:26AM -0700*References*: <20001009220553.0BBD715713@zaphod> <874s2l2ysp.fsf@becket.becket.net> <877l7h1j77.fsf@becket.becket.net> <20001010154823.A1088@colossus.cli.di.unipi.it> <20001010155858.F17938@blueberry.jellybean.co.uk> <20001010114526.A13135@holomorphy.com>

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/

**References**:**Re: Too Many Packages [was Re: Splitting locales...]***From:*Buddha Buck <bmbuck@14850.com>

**Re: Too Many Packages [was Re: Splitting locales...]***From:*tb@becket.net (Thomas Bushnell, BSG)

**Re: Too Many Packages [was Re: Splitting locales...]***From:*tb@becket.net (Thomas Bushnell, BSG)

**Re: Too Many Packages [was Re: Splitting locales...]***From:*Daniele Cruciani <cruciani@cli.di.unipi.it>

**Re: Too Many Packages [was Re: Splitting locales...]***From:*Jules Bean <jules@jellybean.co.uk>

**Re: Too Many Packages [was Re: Splitting locales...]***From:*William Lee Irwin III <wli@holomorphy.com>

- Prev by Date:
**SPI violating bylaws and Debian constitution** - Next by Date:
**Re: Uploaded grub 0.5.96 (source i386) to master** - Previous by thread:
**Re: Too Many Packages [was Re: Splitting locales...]** - Next by thread:
**Re: Too Many Packages [was Re: Splitting locales...]** - Index(es):