On Fri, 16 Nov 2001, Pete Emerson wrote:
> I got this from http://www.wikipedia.com/wiki/Radix_sort:
>
> QUOTE
> Radix sort is a sort algorithm that operates in O(n) time. This algorithm was
> orignally
> used to sort punched cards in several passes. It has resurfaced as an
> alternative to
> other high performance sorting algorithms (like quicksort, heapsort and merge
> sort)
> which run in O(n lg n)) time. Its greatest disadvantages are that it usually
> cannot be
> made to run in place, so O(n) additional memory space is needed, and that it
> requires
> one pass for each symbol of the key, so it is very slow for potentially-long
> keys.
> /QUOTE
Hmmm...this is interesting. A friend of mine who is in the
process of getting her graduate degree in CS/information theory stuff
recently told me that it has been mathematically proven that no sort can
run faster than O(n log n) unless you know something about the incoming
data. I guess that radix sort _only_ works on strings (or stringified
things), then?
> It seems to me if you have some knowledge that the data is unsorted or
> random,
> it might be to your advantage to run the radix algorithm instead.
In general, two principles hold:
- if you know nothing about your data, there are certain
"standard" algorithms/solutions that you pick, because they work well
under most conditions and not too badly even under degenerate cases
(quicksort is an example)
- the more you know about your data
((un)sorted/string/number/limited range), the better you can do at
choosing algorithms that are closer to optimal *for your data*
> Thoughts? Anyone done some testing on actual data? What's that timing module
> again?
perldoc Benchmark.pm
Dave
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
