[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Too Many Packages [was Re: Splitting locales...]



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.

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



Reply to: