Pete Emerson wrote:
>
> Dave Storrs wrote:
>
> > 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?
>
> Radix works on numbers, too; you start with the least significant digit
> and work to the left. Of course, I think of numbers as stringified, anyways.
> There's no difference between base 10 and base n where n is the number of
> characters.
>
> Radix sorts in columns. So, if you are sorting 5 digit numbers, you make
> 5 passes through the data. This would be o(5n), but as n gets huge, the
> contant 5 really doesn't matter, so you drop it and it becomes O(n). Some
> algorithms are O(n^2) but really take o(n^2 + 2n + 1) to run, but big O
> makes it (n^2) because we're interested in what happens as n goes towards
> infinity.
>
> To take a stab at your question about "knowing something about the incoming data",
> and I'm guessing here, we do know how many columns of data we have,
> and therefore know just how big our constant in front of the n is. If this
> constant is too big (bigger than log n I would guess),
> we might want to consider a different sort.
>
> In order to use radix, we'd probably also want to know that our data is not
> "in order" or even "close to order". Part of the problem is that we now are
> taking extra time to look at our data and analyse it before deciding what
> sort to use. Maybe at this point you might want to just use mergesort
> or quicksort and be done with it. I'm going to go mess with Benchmark.pm
> and see what happens.
>
> Okay, maybe it's wandering a little far from Perl Beginners, but it sure is
> interesting!
>
It is indeed
{e}
> Pete
>
> --
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
--
Etienne Marcotte
Specifications Management - Quality Control
Imperial Tobacco Ltd. - Montreal (Qc) Canada
514.932.6161 x.4001
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
