1 import random 2 3 def partition(A, lo, hi): 4 pivot_index = random.randint(lo, hi) 5 pivot = A[pivot_index] 6 A[pivot_index], A[hi] = A[hi], A[pivot_index] 7 store_index = lo 8 for i in range(lo, hi): 9 if A[i] < pivot: 10 A[i], A[store_index] = A[store_index], A[i] 11 store_index = store_index + 1 12 A[store_index], A[hi] = A[hi], A[store_index] 13 return store_index 14 15 def quicksort(A, lo, hi): 16 if lo < hi: 17 p = partition(A, lo, hi) 18 quicksort(A, lo, p - 1) 19 quicksort(A, p + 1, hi) 20 21 if __name__ == '__main__': 22 l = [random.randint(1, 113) for i in range(18)] 23 print l 24 quicksort(l, 0, len(l) - 1) 25 print l