Date: Thu, 26 Feb 98 21:56:10 PST From: Noam Rotem Subject: Re: Sorting Algorythums - bucket sort To: Jan Hubicka Cc: djgpp AT delorie DOT com Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; CHARSET=US-ASCII Precedence: bulk --- On Wed, 25 Feb 1998 11:49:59 +0100 (MET) Jan Hubicka wrote: >is description of Bucket sort available anywhere? I was looking for it >at the net, but no success.. This answer is off-topic but so is the question, so... Bucket sort is based on the assumption of a uniform distribution of values within a given range. Let's say you have 1000 numbers, all between 0 and 1, and uniformly distributed (i.e. the chance of any real number between 0 and 1 to appear in your list is even). Now let's say we have 1000 "buckets". The first represents the range (0,1/1000). The second: (1/1000,2/1000) and so on. The last one is there for (999/1000,1). Now throw each value to the matching bucket, and then sort every bucket separately. If the distribution is indeed uniform, You'll get one value in each bucket, and no more sort is to be done. This algorithm is expected to be of order O(n), because you throw n values into buckets, and almost no other sort is expected. You can implement bucket sort using a hush table and linked lists. You may reduce the number of buckets, without changing the order of runtime (O(2n)=O(3n)=...=O(kn)=O(n)). Radix sort is good when you deal with numbers or strings of the same length (IDs for example), based on an alphabet of k different letters. It is of order O(kn) -> O(n). You can also use: Counting sort (when you sort a group of repeated values within a limited range). Merge sort. Heap sort (which is very good!). --------------------------------------------- Noam Rotem John Bryce Training Centre Tel Aviv, Israel. 03-7535803 ============================================= 1. Take upon yourself an impossible mission. 2. Accomplish the mission. 3. Go back to step 1. It's the only sane answer to modern life. --- 26/02/98 21:56:10