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
Greg Rose (ggr@qualcomm.com)
Fri, 30 Oct 1998 08:28:27 +1000
At 09:41 30/10/98, lots of people wrote words to the effect of:
>Greg Rose wrote:
>> I believe the theoretical minimum is O(n log n) *bits* to randomise n
>> items. (This agrees entirely with the above, given that the random numbers
>> are log n bits each.) But another, 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.
>
>Beware - quicksort really hates this, and many implementations will
>either crash or hang if you don't make consistent decisions. The
>preferred approach is to give each thing you want to shuffle a random
>number, then sort the random numbers.
I wasn't suggesting anyone *do* this. I was just noting its theoretical
interest. (By the way, Hoare's original heapsort works just fine this way. :-)
Knuth's algorithm is clearly the best and most efficient way to do it (and
it's correct too, unlike some of the suggestions). It requires no extra
storage, and randomises in n calls to a log-n-bit generator, and n swaps.
Sorting an ancillary array requires extra memory, and n calls to a random
generator generating significantly more than log-n bits each time (as
duplicates must be unlikely) then n log n compares and swaps; this is
clearly much less efficient.
Some people are wayyy too literal. :-)
Greg.
Greg Rose INTERNET: ggr@Qualcomm.com
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23