I think i can address why this shuffle isnt fair. (sort of)

To simplify things, i am going to pretend that the built in sort uses a bubble sort (i honestly dont know what algorithm is used behind the scenes), but similar arguments can be applied to whatever sort() really uses.

So, recall that the 'largest' element will be bubbled to the last element in the array after 1 iteration, the second largest after the second iteration, and so on.

For this example, regardless of what happens prior to the final 2 elements being compared on the first iteration, when the final 2 elements are compared, there is a 50-50 chance that the final element will stay in place - provided rand() is fair.

If the final element is bubbled back, then on the second iteration it has a 50-50 chance of staying in the second last position. And after the 50-50 of staying in the final position, that makes a 25% chance of staying in the second last place. And so on and so on.

The chance of various other elements ending up in various places could be similarly calculated.

That said, recall that i assumed a bubble sort. I leave it as an exercise to the reader to perform similar analysis on other sort algorithms

(how cocky of me!)

In reply to Re: Is this a fair shuffle? by shemp
in thread Is this a fair shuffle? by Roy Johnson

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.