Unsorting(randomizing) a sequence

[Ian Clarke]

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

def timing(f, n, a):
    """
    A timing function borrowed from
    http://www.python.org/doc/essays/list2str.html
    """
    print f.__name__,
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
    t2 = time.clock()
    print round(t2-t1, 3)

def s1(list):
    """Dan Schmidt's solution - (mis)using sort"""
    def randomize(a,b):
        return random.choice([-1, 0, 1])
    list.sort(randomize)
    return 

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

def s3(list):
    """Skip Montanaro's solution as fixed by Dan Schmidt"""
    for i in range(len(list)-1, 0, -1):
        choice = int(whrandom.randint(0,i))
        list[choice], list[i] = list[i], list[choice]

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

def s5(ar):
    """Ian Clarke's solution"""
    for i in range(len(ar)-1,0,-1):
        choice = int(whrandom.randint(0,i))
        ar[choice], ar[i] = ar[i], ar[choice]
    return ar

timing(s1, 10, range(200))
timing(s2, 10, range(200))
timing(s3, 10, range(200))
timing(s4, 10, range(200))
timing(s5, 10, array.array('b', range(200)))