Date: Fri, 27 Feb 1998 11:43:46 +0100 (MET)
From: Jan Hubicka <hubicka AT ta DOT jcu DOT cz>
To: Noam Rotem <nrotem AT johnbryce DOT co DOT il>
cc: djgpp AT delorie DOT com
Subject: Re: Sorting Algorythums - bucket sort 
In-Reply-To: <Chameleon.980226221729.nrotem@netvision.netvision>
Message-ID: <Pine.LNX.3.95.980227113911.26713B-100000@tabor.ta.jcu.cz>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk

On Thu, 26 Feb 1998, Noam Rotem wrote:

> 
> --- On Wed, 25 Feb 1998 11:49:59 +0100 (MET)  Jan Hubicka <hubicka AT ta DOT jcu DOT cz> 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...
thank you very much...
> 
> 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. 
OK, so that means, that I simply divide interval <0,1> to 1000 parts and
then sort them as integers? (in O(N) using distribution sort) and then
just sort small amounts of numbers inside one interval (bucket)?
that seems to be simple :)
> 
> 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!).
OK
Thank you for your reply..

Honza
> 
> ---------------------------------------------
> 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
> 

------------------------------------------------------------------------------
                   Have you browsed my www pages? Look at:
                       http://www.paru.cas.cz/~hubicka
      Koules-the game for Svgalib,X11 and OS/2,  Xonix-the game for X11
      czech documentation for linux index, original 2D computer art and
              funny 100 years old photos and articles are there!