Unsorting(randomizing) a sequence

[Rob Hooft]

>>>>> "JH" == Jeremy Hylton <jeremy at cnri.reston.va.us> writes:

 >> The "hylton" method favors even permutations over odd ones, tends
 >> to produce increasing sequences, and distributes the variance
 >> unequally, apparently peaking near the beginning (1/e of the way
 >> through?).  I haven't quite fully analyzed the reasons for this
 >> yet...

 JH> I expect that the reason its tends to produce increasing
 JH> sequences is that you started with a sorted sequence; if you
 JH> reverse the sequence, it will probably tend towards decreasing
 JH> sequences.  I think this follows from the quicksort approach.
 JH> Quicksort is going to divide each list into two sublists where
 JH> the each element of the first sublist is less than or equal to
 JH> each element of the second sublist.

 JH> Since the comparison function is random, the sort is just going
 JH> to exchange a random number of elements around the pivot point.
 JH> Then quicksort is going to be applied to each sublist, so no
 JH> element from the second sublist is ever going to be moved to the
 JH> other side of the original pivot point.  The end result is that
 JH> the shufflesort method will often leave elements close to where
 JH> they were originally.

You can improve the "randomness" performance significantly (still not
making it good) by making the random process never return 0. It is too
complicated for me to go through the quicksort algorithm, but you can
easily see that returning one of -1,0,1 makes a simple sort algorithm
leave 2/3 of the orders the same, and swap only 1/3. This gives a bias
towards the original order.

Rob
-- 
=====   R.Hooft at EuroMail.net   http://www.xs4all.nl/~hooft/rob/  =====
=====   R&D, Nonius BV, Delft  http://www.nonius.nl/             =====
===== PGPid 0xFA19277D ========================== Use Linux! =========