quicksort

quicksort.py

import random
import sys
import time

def quicksort(a, left, right):
    if left < right:
        p = left
        k = left + 1
        while k <= right:
            if a[k] < a[left]:
                tmp = a[p + 1]
                a[p + 1] = a[k]
                a[k] = tmp
                p += 1
            k += 1
        tmp = a[left]
        a[left] = a[p]
        a[p] = tmp
        a = quicksort(a, left, p - 1)
        a = quicksort(a, p + 1, right)
    return a

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

if __name__ == '__main__':
    main()