Mail Archives: djgpp/1998/02/27/04:53:05
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!
- Raw text -