#!/usr/bin/python3

# Quick Sort 快速排序
# 基于《算法导论》第七章

import random

A = []
for i in range(1000000):
    A.append(random.randint(0, 999999))

def parition(A, p, r):
    pivot = A[r]
    i = p - 1

    for q in range(p, r):
        if A[q] < pivot:
            i += 1
            tmp = A[i]
            A[i] = A[q]
            A[q] = tmp

    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp

    return i+1

def quicksort(A, p, r):
    if p < r:
        q = parition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

quicksort(A, 0, len(A)-1)