qsort.py

# -*- coding: utf-8 -*-
from __future__ import print_function
import timeit, random, sys

if sys.version_info >= (3, ): xrange=range

def partition(data, begin, end):
    value = data[end-1]
    pivot = begin

    for i in xrange(begin, end-1):
        if data[i] < value:
            data[pivot], data[i] = data[i], data[pivot]
            pivot += 1
    
    data[pivot], data[end-1] = data[end-1], data[pivot]
    return pivot
    
def qsort(data, begin, end):
    while begin+1 < end:
        pivot = partition(data, begin, end)
        if pivot-begin < end-pivot:
            qsort(data, begin, pivot)
            begin = pivot+1
        else:
            qsort(data, pivot+1, end)
            end = pivot


V = random.sample(xrange(1,99999999),1000000)
print(timeit.timeit(lambda: qsort(V, 0, len(V)), number=1))