Mail Archives: djgpp/1998/02/26/15:21:05
--- 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...
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
- Raw text -