# Unsorting(randomizing) a sequence

Guido van Rossum guido at cnri.reston.va.us
Thu Aug 19 14:35:15 EDT 1999

```Ian Clarke <I.Clarke at strs.co.uk> writes:

> I did some timing tests using the code I have attached below, here are
> the results (in seconds) for sorting a list of 200 items 10 times:
>
> Dan Schmidt's solution (using sort): 14.98
> Stephan Houben's solution          : 2.82
> Skip Montanaro's solution          : 2.736
>  (as modified by Dan schmidt)
> Magnus L Hetland's solution        : 0.032
> Skip's solution but with arrays    : 3.182
>
> As you can see I thought that using arrays may provide an efficiency
> speed-up for Skip's algorithm, but apparently not.  Oh, I haven't really
> checked this code too carefully, so feel free to redo the tests if you
> find any bugs in the code.
>
> Magnus L Hetland's solution wins hands down.

The two-orders-of-magnitude-faster result should have made you look
twice.  There's a bug: s4(list) modifies its argument (empyting it) so
you did only one run, plus 9 runs of an empty list!  Corrected, I get
these timings (on a slightly faster machine, it seems):

s1 12.1
s2 2.31
s3 2.63
s4 2.68
s5 2.82

Here's the fixed s4():

def s4(list):
"""Magnus L Hetland's solution"""
result = []
list = list[:]
for i in range(len(list)):
element = random.choice(list)
list.remove(element)
result.append(element)
return result

But the winner is Tim Peters' entry, already in the CVS tree.  Its
time is 1.34 seconds:

def shuffle(x, random=random, int=int):
"""x, random=random.random -> shuffle list x in place; return None.

Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.

Note that for even rather small len(x), the total number of
permutations of x is larger than the period of most random number
generators; this implies that "most" permutations of a long
sequence can never be generated.
"""

for i in xrange(len(x)-1, 0, -1):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]