quicksort.py

def quicksort(list):
    if len(list) <= 1:
        return list
    pivot = list[0]
    left = []
    right = []
    for val in list[1:len(list)]:
        if val < pivot:
            left.append(val)
        else:
            right.append(val)
    left = quicksort(left)
    right = quicksort(right)
    return left + [pivot] + right

def q_sort(ori_list):
    if len(ori_list) == 0 : return ori_list
    pivot = ori_list.pop()
    min_list =  [x for x in ori_list if x <=  pivot ]
    max_list =  [x for x in ori_list if x >   pivot ]
    return  q_sort(min_list) + [pivot] + q_sort(max_list)

if __name__ == "__main__":
    list = [3, 4, 7, 1, 8, 2, 9, 5]
    print quicksort(list)
    print q_sort(list)