Unsorting(randomizing) a sequence
tim_one at email.msn.com
Tue Aug 17 21:20:21 EDT 1999
> The "shufflesort" or "Tim Peters" method, which I would offer as
> preferred names (because I don't particularly want my name associated
> with it and Tim's name is as good as anyone's),
Indeed, I'm *thrilled* to be associated with this worthless method, Jeremy!
I must have it inscribed on my tombstone.
> depends an awful lot on the Python quicksort implementation (another
> good reason to call it the Tim Peter's method <wink>).
Since Python no longer uses a quicksort, that's even more appropriate
[attempting to explain shufflesort's bad behavior]
> I think this follows from the quicksort approach.
It certainly depends on the details of the sort implementation. For the
size of inputs you've been looking at, Python actually uses a pure binary
insertion sort after finding the longest already-sorted prefix, and the only
comparison outcome it looks at is the two-way "less than, or not?". Your
choice function gives equal weights to -1, 0 and 1, the latter two of which
the sort takes as meaning "no".
For the two-element case, it will leave the input alone 75% of the time.
Now you'll have no problem completing an exact analysis for the general case
almost-done-with-the-N=1-case-myself-ly y'rs - tim
More information about the Python-list