import random
def quicksort(L):
ln = len(L)
def _xchg(_A, _l, _r):
t = _A[_l]
_A[_l] = _A[_r]
_A[_r] = t
def _rand_part(A, p, r):
def _part(_A, _p, _r):
x = _A[_r - 1]
i = _p
for j in range(_p, _r - 1):
if _A[j] < x:
_xchg(_A, i, j)
i += 1
_xchg(_A, i, _r - 1)
return i
i = random.randrange(p, r)
_xchg(A, i, r - 1)
return _part(A, p, r)
def _quicksort(A, p, r):
if p < r:
q = _rand_part(A, p, r)
_quicksort(A, p, q)
_quicksort(A, q + 1, r)
_quicksort(L, 0, ln)
if __name__ == '__main__':
import sys
num = 100
if len(sys.argv) == 2:
num = int(sys.argv[1])
L = [ random.randrange(10, 1000) for x in range(num) ]
print L
quicksort(L)
print L
|
