Re: Bucket sort, ouch!
Hendy Irawan writes:
> What is it, really? What's the heart of it? Where can I get more
> info? What kind of data is good for bucket sort? And why everybody
> is using Quicksort if there's a better algo?
Quicksort is a fast, general-purpose sorting algorithm.
"Bucket" sort (also known as "radix" sort or "distribution counting")
is even faster, but the data you are sorting must have some
nice properties. Bucket sort is ideally suited to sorting integers
where the range of possible values in the input data is small enough
that you can afford to create a bucket (i.e. a sequence element)
for each possible value, and simply count the occurrences. That gives you
an "order N" sort, whereas quicksort is "order N logN".
You might also create buckets to hold a consecutive *range* of
values, then later sort each of those buckets (like my string sort).
Sorting many small sequences of values is faster than
sorting one huge sequence of values.
You could also write a recursive bucket sort that would use itself
to sort the individual buckets - I found it was better to just use
Euphoria's shell sort for the individual buckets.
The bucket sort algorithm can be adapted to work on
floating-point numbers and other data too. The problem is
it has to be adapted somewhat for each type of data.
For a complete (huge) study of dozens of sorting methods,
see Donald Knuth's "The Art of Computer Programming",
Vol 3 - Sorting and Searching.
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
|
Not Categorized, Please Help
|
|
