[104859] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (Jim Gillogly)
Thu Oct 29 23:29:58 1998
Date: Thu, 29 Oct 1998 20:04:57 -0800
From: Jim Gillogly <jim@acm.org>
To: coderpunks@toad.com
Reply-To: Jim Gillogly <jim@acm.org>
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.
"David R. Conrad" <drc@adni.net> responded:
> The only caveat here is to make sure that this doesn't mung the operation
> of the sort.
One could modify Greg's suggestion slightly by attaching an auxiliary
array of 256 random numbers to each of the members of the original
array and then using the most efficient handy sort algorithm to sort
those random numbers, dragging along their associated original array
elements. This way it doesn't have a chance to interfere with the
operation of the sorting algorithm, at the cost of an extra array.
--
Jim Gillogly
Trewesday, 9 Blotmath S.R. 1998, 04:00
12.19.5.11.11, 9 Chuen 4 Zac, Sixth Lord of Night
