Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23
David R. Conrad (drc@adni.net)
Thu, 29 Oct 1998 21:24:47 -0500 (EST)
On Thu, 29 Oct 1998, Greg Rose wrote:
> [A]nother, theoretically interesting, way to
> randomise is to take a sorting algorithm and make random binary choices
> everywhere it would compare two elements and swap them if out of order.
The only caveat here is to make sure that this doesn't mung the operation
of the sort. Some sorts have a test "Were any swaps made that pass? If
so, rerun." I know you're thinking, "I'm not going to use bubblesort, you
dunce," but keep in mind that many implementations of quicksort only
divide-and-conquer down to a certain level, then use a simpler sort when
they get small enough groups.
Quicksort will do fine with random decisions, splitting items into roughly
equal groups of two, or three if you're using a three-way partition
version of quicksort, but if it uses another sort for small chunks then
make sure that it doesn't iterate endlessly as long as swaps are taking
place, otherwise you'll wait an awfully long time for the sort to
complete. :-)
And, still, this isn't as good as the O(n) algorithm that has now been
referred to a number of times. Particularly, if you need more random
numbers and you're getting them from BBS, it could greatly increase the
time required for the sort (BBS being so slow). If you're getting them
from a physical source, you probably don't care, but you might. And if
you're living in sin and generating them algorithmically, the more you use
the better an attacker's chance of figuring out the state of your
generator, although in this case that seems pretty implausible to my
admitted untrained eye.
Coming soon: a summary of the many useful suggestions I received regarding
my question about java applets and a proposed protocol.
Note: please don't Cc: me on replies; I'm on the list and I don't need
duplicate copies of everything.
David R. Conrad <drc@adni.net>
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23