Unsorting(randomizing) a sequence

[Stephan Houben]

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

D> 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.
> 
> Ian.
> 
> ---
> import random, array, time

You should also import whrandom for Skip's solution. 

Frankly, I'm pretty much baffled by these results.
Ian's, Skip's and mine solution all use simple swaps.
However, Magnus' solution keeps removing and appending items to lists.

And now it turns out that Magnus' approach is *faster*?
How can this be?
I demand immediate explanation! <0.999 wink>

By the way, my code could be tuned just a little more:

def s2(list): 
    """Stephan Houben's solution""" 
    length = len(list)
    randrange = random.randrange
    for i in range(length): 
        j = randrange(i, length)
	tmp = list[i]
	list[i] = list[j]
	list[j] = tmp

However, it's still far from being in the same ball park
as Magnus' code.

I'm heavily disappointed in myself.

Greetings,

Stephan