randomized quicksort

randomized_auicksort.py

import random
import time

def randomized_quicksort(a, left, right):
    if left < right:
        r = random.randint(left, right)
        a[r], a[left] = a[left], a[r]
        p = left
        k = left + 1
        while k <= right:
            if a[k] < a[left]:
                a[p + 1], a[k] = a[k], a[p + 1]
                p += 1
            k += 1
        a[left], a[p] = a[p], a[left]
        a = randomized_quicksort(a, left, p - 1)
        a = randomized_quicksort(a, p + 1, right)
    return a

def main():
    random.seed(100)
    c = [random.randint(0,1000000) for i in range(1000000)]
    random.seed()
    print "start"
    s = time.time()
    d = randomized_quicksort(c,0,len(c)-1);
    e = time.time()
    print "time: %f" % (e - s)
    c.sort()
    print c == d

if __name__ == '__main__':
    main()