quick_sort.py

# coding: utf-8
import random

def quick_sort(inlist):
    if len(inlist) <= 1:
        return inlist
    middle = len(inlist) / 2
    pivot = inlist.pop(middle)
    left, right = [], []
    for i in inlist:
        if i <= pivot:
            left.append(i)
        else:
            right.append(i)
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [pivot] + right

def isSort(inlist):
    for i in xrange(len(inlist) - 1):
        if inlist[i] > inlist[i+1]:
            return False
    return True

if __name__ == "__main__":
    testlist = range(100)
    random.shuffle(testlist)
    assert isSort(testlist) == False
    after = quick_sort(testlist)
    assert isSort(after) == True